提交记录 9287


用户 题目 状态 得分 用时 内存 语言 代码长度
beretty noip18d. 【NOIP2018】旅行 Accepted 100 275.426 ms 36332 KB C++11 2.90 KB
提交时间 评测时间
2019-04-22 16:48:28 2020-08-01 01:35:25
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int M = 20055 ;
using namespace std ;
inline int read() {
    char c = getchar() ; int x = 0 , w = 1 ;
    while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }
    while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }
    return x*w ;
}

int n , m ;
int hea[M] , num ;
int temp[M] , tot , Ans[M] ;
bool vis[M] , use[M] ;
vector < int > e[M] ;
int dfn[M] , low[M] , cnt ;
int bel[M] , st[M] , top , sz ;
bool exist[M] ;
int id[5005][5005] ;
struct E {
    int Nxt , From , to ;
} edge[M] ;
inline void add_edge(int from , int to) {
    edge[++num].Nxt = hea[from] ;
    edge[num].From = from ;
    edge[num].to = to ; hea[from] = num ;
}

void Dfs(int u , int father) {
    temp[++tot] = u ;
    for(int i = hea[u] ; i ; i = edge[i].Nxt) {
        int v = edge[i].to ;
        if(v == father || vis[i]) continue ;
        Dfs(v , u) ;
    }
}
inline void Solve1() {
    Dfs(1 , 1) ;
    for(int i = 1 ; i <= tot ; i ++) printf("%d ",temp[i]) ;
}
void tarjan(int u , int father) {
    dfn[u] = low[u] = ++cnt ; exist[u] = true ; st[++top] = u ;
    for(int i = hea[u] ; i ; i = edge[i].Nxt) {
        int v = edge[i].to ;
        if(v == father) continue ;
        if(!dfn[v]) {
            tarjan(v , u) ;
            low[u] = min(low[u] , low[v]) ;
        }
        if(exist[v]) low[u] = min(low[u] , dfn[v]) ;
    }
    if(dfn[u] == low[u]) {
        ++ sz ;
        while(st[top + 1] != u) {
            bel[st[top]] = sz ;
            exist[st[top --]] = false ;
        }
    }
}
inline bool chkmin() {
    for(int i = 1 ; i <= tot ; i ++){
        if(Ans[i] > temp[i]) return true ;
        else if(Ans[i] < temp[i]) return false ;
    }
    return false ;
}
inline void Solve2() {
    for(int i = 1 ; i <= n ; i ++)
        if(!dfn[i])
            tarjan(i , i) ;
    memset(Ans , 63 , sizeof(Ans)) ;
    for(int i = 1 , u , v ; i <= num ; i ++) {
        u = edge[i].From , v = edge[i].to ;
        if(bel[u] != bel[v]) continue ;
        if(use[id[u][v]] || use[id[v][u]]) continue ;
        use[id[u][v]] = use[id[v][u]] = true ;
        vis[id[u][v]] = vis[id[v][u]] = true ;
        tot = 0 ;
        Dfs(1 , 1) ;
        vis[id[u][v]] = vis[id[v][u]] = false ;
        if(chkmin())
            for(int j = 1 ; j <= tot ; j ++)
                Ans[j] = temp[j] ;
    }
    for(int i = 1 ; i <= n ; i ++) printf("%d ",Ans[i]) ;
}
int main() {
    n = read() , m = read() ;
    for(int i = 1 , u , v ; i <= m ; i ++) {
        u = read() , v = read() ;
        e[u].push_back(v) ;
        e[v].push_back(u) ;
    }
    for(int i = 1 ; i <= n ; i ++) {
        sort(e[i].begin() , e[i].end()) ;
        for(int j = e[i].size() - 1 , v ; j >= 0 ; j --) {
            v = e[i][j] ;
            add_edge(i , v) ;
            id[i][v] = num ;
        }
    }
    if(m == n - 1) {
    	Solve1() ;
    	return 0 ;
    }
    else Solve2() ;
    return 0 ;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1113.31 us560 KBAcceptedScore: 4

Testcase #2118.3 us560 KBAcceptedScore: 4

Testcase #3110.76 us560 KBAcceptedScore: 4

Testcase #4162.13 us932 KBAcceptedScore: 4

Testcase #5157.47 us940 KBAcceptedScore: 4

Testcase #6672.66 us5 MB + 820 KBAcceptedScore: 4

Testcase #7673.79 us5 MB + 844 KBAcceptedScore: 4

Testcase #8672.54 us5 MB + 856 KBAcceptedScore: 4

Testcase #9658.92 us5 MB + 552 KBAcceptedScore: 4

Testcase #10661.74 us5 MB + 564 KBAcceptedScore: 4

Testcase #113.499 ms34 MB + 916 KBAcceptedScore: 4

Testcase #123.511 ms35 MB + 20 KBAcceptedScore: 4

Testcase #133.52 ms35 MB + 280 KBAcceptedScore: 4

Testcase #143.493 ms34 MB + 936 KBAcceptedScore: 4

Testcase #153.534 ms35 MB + 416 KBAcceptedScore: 4

Testcase #16121.76 us664 KBAcceptedScore: 4

Testcase #17121.09 us664 KBAcceptedScore: 4

Testcase #18205.96 us1 MB + 24 KBAcceptedScore: 4

Testcase #19203.1 us1 MB + 16 KBAcceptedScore: 4

Testcase #208.546 ms5 MB + 924 KBAcceptedScore: 4

Testcase #218.518 ms5 MB + 924 KBAcceptedScore: 4

Testcase #228.859 ms6 MB + 12 KBAcceptedScore: 4

Testcase #23275.426 ms35 MB + 492 KBAcceptedScore: 4

Testcase #24260.911 ms35 MB + 100 KBAcceptedScore: 4

Testcase #25247.084 ms35 MB + 60 KBAcceptedScore: 4


Judge Duck Online | 评测鸭在线
Server Time: 2020-10-31 13:13:13 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用