답안 #631479

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
631479 2022-08-18T07:35:25 Z bachhoangxuan Pipes (BOI13_pipes) C++17
41.4815 / 100
202 ms 14644 KB
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
#define pii pair<int,int>
vector<pii> edge[maxn];
int n,m,c[maxn],st,num=0,ans[maxn];
bool check[maxn],visited[maxn];
bool dfs(int u,int par){
    bool ok=false;visited[u]=true;
    for(pii x:edge[u]){
        int v=x.first;
        if(v==par) continue;
        if(visited[v]){st=v;ok=true;}
        else if(dfs(v,u)) ok=true;
    }
    if(ok){check[u]=true;num++;}
    if(st==u){st=0;return false;}
    if(ok) return true;
    return false;
}
void dfs2(int u,int par){
    for(pii v:edge[u]){
        if(v.first==par || check[v.first]) continue;
        dfs2(v.first,u);
        ans[v.second]=c[v.first];
        c[u]+=c[v.first];
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n >> m;
    if(m>n){
        cout << 0 << '\n';
        return 0;
    }
    for(int i=1;i<=n;i++) cin >> c[i];
    for(int i=1;i<=m;i++){
        int u,v;cin >> u >> v;
        edge[u].push_back({v,i});
        edge[v].push_back({u,i});
    }
    dfs(1,0);
    if(num%2==0 && m==n){
        cout << 0 << '\n';
        return 0;
    }
    for(int i=1;i<=n;i++){
        if(check[i]) dfs2(i,0);
    }
    if(m!=n) dfs2(1,0);
    int cur=0,u=0;
    for(int i=1;i<=n;i++){
        if(check[i]){cur=i;u=i;break;}
    }
    while(true){
        for(pii v:edge[u]){
            if(check[v.first]){
                ans[v.second]=c[u];
                c[v.first]+=c[u];
                u=v.first;
                break;
            }
        }
        if(u==cur) break;
    }
    for(int i=1;i<=m;i++) cout << ans[i]*2 << '\n';
}
# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 2644 KB Output isn't correct
2 Incorrect 1 ms 2644 KB Output isn't correct
3 Incorrect 5 ms 2696 KB Output isn't correct
4 Incorrect 88 ms 7640 KB Output isn't correct
5 Incorrect 2 ms 2644 KB Output isn't correct
6 Incorrect 2 ms 2644 KB Output isn't correct
7 Incorrect 3 ms 2648 KB Output isn't correct
8 Incorrect 2 ms 2668 KB Output isn't correct
9 Incorrect 3 ms 2644 KB Output isn't correct
10 Incorrect 2 ms 2644 KB Output isn't correct
11 Incorrect 2 ms 2644 KB Output isn't correct
12 Incorrect 2 ms 2644 KB Output isn't correct
13 Incorrect 46 ms 6668 KB Output isn't correct
14 Incorrect 76 ms 7392 KB Output isn't correct
15 Incorrect 202 ms 7756 KB Output isn't correct
16 Incorrect 49 ms 6888 KB Output isn't correct
17 Incorrect 69 ms 7728 KB Output isn't correct
18 Incorrect 60 ms 7628 KB Output isn't correct
19 Incorrect 62 ms 11168 KB Output isn't correct
20 Incorrect 2 ms 2644 KB Output isn't correct
21 Incorrect 2 ms 2644 KB Output isn't correct
22 Incorrect 54 ms 7756 KB Output isn't correct
23 Incorrect 48 ms 6692 KB Output isn't correct
24 Incorrect 67 ms 7764 KB Output isn't correct
25 Incorrect 61 ms 6840 KB Output isn't correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2656 KB Output isn't correct
2 Incorrect 2 ms 2772 KB Output isn't correct
3 Correct 47 ms 9876 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 1 ms 2644 KB Output is correct
7 Incorrect 1 ms 2644 KB Output isn't correct
8 Incorrect 2 ms 2644 KB Output isn't correct
9 Incorrect 4 ms 2644 KB Output isn't correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 1 ms 2644 KB Output is correct
14 Incorrect 2 ms 2652 KB Output isn't correct
15 Incorrect 2 ms 2772 KB Output isn't correct
16 Incorrect 2 ms 2656 KB Output isn't correct
17 Correct 4 ms 2656 KB Output is correct
18 Correct 3 ms 2644 KB Output is correct
19 Correct 2 ms 2644 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 1 ms 2644 KB Output is correct
22 Incorrect 3 ms 2696 KB Output isn't correct
23 Incorrect 66 ms 10448 KB Output isn't correct
24 Incorrect 102 ms 11480 KB Output isn't correct
25 Correct 73 ms 9864 KB Output is correct
26 Correct 3 ms 2644 KB Output is correct
27 Correct 2 ms 2644 KB Output is correct
28 Correct 2 ms 2644 KB Output is correct
29 Correct 2 ms 2644 KB Output is correct
30 Incorrect 68 ms 13116 KB Output isn't correct
31 Incorrect 102 ms 13868 KB Output isn't correct
32 Incorrect 94 ms 8976 KB Output isn't correct
33 Correct 78 ms 10820 KB Output is correct
34 Correct 2 ms 2644 KB Output is correct
35 Correct 2 ms 2644 KB Output is correct
36 Correct 2 ms 2644 KB Output is correct
37 Correct 2 ms 2644 KB Output is correct
38 Incorrect 114 ms 13004 KB Output isn't correct
39 Incorrect 96 ms 8464 KB Output isn't correct
40 Incorrect 63 ms 10440 KB Output isn't correct
41 Correct 65 ms 13236 KB Output is correct
42 Correct 2 ms 2644 KB Output is correct
43 Correct 2 ms 2644 KB Output is correct
44 Correct 2 ms 2644 KB Output is correct
45 Correct 2 ms 2688 KB Output is correct
46 Incorrect 76 ms 14644 KB Output isn't correct
47 Incorrect 59 ms 10504 KB Output isn't correct
48 Incorrect 59 ms 13644 KB Output isn't correct
49 Incorrect 65 ms 8572 KB Output isn't correct
50 Correct 2 ms 2644 KB Output is correct
51 Correct 2 ms 2644 KB Output is correct
52 Correct 2 ms 2644 KB Output is correct
53 Correct 1 ms 2644 KB Output is correct
54 Incorrect 82 ms 12364 KB Output isn't correct