# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
111629 | 2019-05-15T21:54:09 Z | wilwxk | Pipes (BOI13_pipes) | C++11 | 495 ms | 27244 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=2e5+5; vector<int> g[MAXN], lista[MAXN]; vector<int> ncyc; ll v[MAXN], tenho[MAXN]; int gin[MAXN]; ll resp[MAXN], soma; int n, m; void poda() { queue<int> qu; for(int i=1; i<=n; i++) if(gin[i]==1) qu.push(i); while(!qu.empty()) { int cur=qu.front(); qu.pop(); gin[cur]=0; ncyc.push_back(cur); for(int i=0; i<g[cur].size(); i++) { int viz=g[cur][i]; int ind=lista[cur][i]; if(!gin[viz]) continue; gin[viz]--; if(gin[viz]<=1) qu.push(viz); resp[ind]=v[cur]-tenho[cur]; tenho[viz]+=resp[ind]; tenho[cur]+=resp[ind]; // printf("%d -> %d (%d, %lld)\n", cur, viz, ind, tenho[cur]); } } } void dfs(int cur, int k) { // printf("%d %d\n", cur, k); gin[cur]=1; for(int i=0; i<g[cur].size(); i++) { int viz=g[cur][i]; int ind=lista[cur][i]; if(gin[viz]!=2) continue; dfs(viz, k^1); } if(!k) soma+=v[cur]; else soma-=v[cur]; } void solve(int cur, int p) { gin[cur]=2; for(int i=0; i<g[cur].size(); i++) { int viz=g[cur][i]; int ind=lista[cur][i]; if(viz==p||gin[viz]!=1) continue; if(cur==p) resp[ind]=soma; else resp[ind]=v[cur]-tenho[cur]; tenho[viz]+=soma; // tenho[cur]+=soma; solve(viz, cur); } } int main() { scanf("%d %d", &n, &m); for(int i=1; i<=n; i++) scanf("%lld", &v[i]), v[i]*=2; for(int i=1; i<=m; i++) { int a, b; scanf("%d %d", &a, &b); g[a].push_back(b); g[b].push_back(a); gin[a]++; gin[b]++; lista[a].push_back(i); lista[b].push_back(i); } poda(); for(int i=1; i<=n; i++) if(gin[i]) v[i]-=tenho[i], tenho[i]=0; // for(int i=1; i<=n; i++) cout << v[i] << endl; if(m>n||(n-ncyc.size())%2==0) { printf("0\n"); return 0; } if(m==n-1&&tenho[ncyc.back()]!=v[ncyc.back()]) { printf("0\n"); return 0; } for(int i=1; i<=n; i++) { if(!gin[i]) continue; dfs(i, 0); // printf("ok %lld\n", soma); solve(i, i); break; } bool ok=1; for(int i=1; i<=n; i++) if(tenho[i]!=v[i]) ok=0; if(ok) { for(int i=1; i<=m; i++) printf("%lld\n", resp[i]); } else { printf("0\n"); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 9728 KB | Output is correct |
2 | Correct | 10 ms | 9728 KB | Output is correct |
3 | Correct | 13 ms | 9856 KB | Output is correct |
4 | Correct | 147 ms | 20132 KB | Output is correct |
5 | Correct | 9 ms | 9728 KB | Output is correct |
6 | Correct | 9 ms | 9728 KB | Output is correct |
7 | Correct | 9 ms | 9728 KB | Output is correct |
8 | Correct | 9 ms | 9728 KB | Output is correct |
9 | Correct | 10 ms | 9856 KB | Output is correct |
10 | Correct | 12 ms | 9856 KB | Output is correct |
11 | Correct | 10 ms | 9856 KB | Output is correct |
12 | Correct | 10 ms | 9856 KB | Output is correct |
13 | Correct | 102 ms | 18000 KB | Output is correct |
14 | Correct | 166 ms | 19440 KB | Output is correct |
15 | Correct | 146 ms | 20160 KB | Output is correct |
16 | Correct | 111 ms | 18544 KB | Output is correct |
17 | Correct | 146 ms | 20080 KB | Output is correct |
18 | Correct | 147 ms | 20168 KB | Output is correct |
19 | Correct | 160 ms | 19720 KB | Output is correct |
20 | Correct | 9 ms | 9728 KB | Output is correct |
21 | Correct | 11 ms | 9856 KB | Output is correct |
22 | Correct | 142 ms | 20300 KB | Output is correct |
23 | Correct | 114 ms | 18032 KB | Output is correct |
24 | Correct | 142 ms | 20012 KB | Output is correct |
25 | Correct | 118 ms | 18416 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 10 ms | 9728 KB | Output isn't correct |
2 | Incorrect | 9 ms | 9856 KB | Output isn't correct |
3 | Correct | 118 ms | 18864 KB | Output is correct |
4 | Correct | 102 ms | 19048 KB | Output is correct |
5 | Correct | 97 ms | 19416 KB | Output is correct |
6 | Correct | 403 ms | 27216 KB | Output is correct |
7 | Incorrect | 9 ms | 9728 KB | Output isn't correct |
8 | Incorrect | 9 ms | 9728 KB | Output isn't correct |
9 | Correct | 10 ms | 9728 KB | Output is correct |
10 | Correct | 10 ms | 9728 KB | Output is correct |
11 | Correct | 10 ms | 9728 KB | Output is correct |
12 | Correct | 9 ms | 9728 KB | Output is correct |
13 | Correct | 10 ms | 9856 KB | Output is correct |
14 | Incorrect | 11 ms | 9728 KB | Output isn't correct |
15 | Incorrect | 9 ms | 9856 KB | Output isn't correct |
16 | Incorrect | 11 ms | 9856 KB | Output isn't correct |
17 | Correct | 10 ms | 9856 KB | Output is correct |
18 | Correct | 9 ms | 9856 KB | Output is correct |
19 | Correct | 10 ms | 9856 KB | Output is correct |
20 | Correct | 10 ms | 9856 KB | Output is correct |
21 | Correct | 10 ms | 9856 KB | Output is correct |
22 | Incorrect | 10 ms | 9856 KB | Output isn't correct |
23 | Incorrect | 146 ms | 20540 KB | Output isn't correct |
24 | Incorrect | 153 ms | 22420 KB | Output isn't correct |
25 | Correct | 110 ms | 18920 KB | Output is correct |
26 | Correct | 108 ms | 19064 KB | Output is correct |
27 | Correct | 99 ms | 18968 KB | Output is correct |
28 | Correct | 135 ms | 19512 KB | Output is correct |
29 | Correct | 295 ms | 25108 KB | Output is correct |
30 | Incorrect | 165 ms | 21736 KB | Output isn't correct |
31 | Incorrect | 157 ms | 24440 KB | Output isn't correct |
32 | Incorrect | 119 ms | 20592 KB | Output isn't correct |
33 | Correct | 116 ms | 19360 KB | Output is correct |
34 | Correct | 133 ms | 19088 KB | Output is correct |
35 | Correct | 101 ms | 19064 KB | Output is correct |
36 | Correct | 106 ms | 19444 KB | Output is correct |
37 | Correct | 495 ms | 27244 KB | Output is correct |
38 | Incorrect | 179 ms | 22068 KB | Output isn't correct |
39 | Incorrect | 159 ms | 20168 KB | Output isn't correct |
40 | Incorrect | 176 ms | 22320 KB | Output isn't correct |
41 | Correct | 114 ms | 18888 KB | Output is correct |
42 | Correct | 124 ms | 18808 KB | Output is correct |
43 | Correct | 99 ms | 18808 KB | Output is correct |
44 | Correct | 171 ms | 19500 KB | Output is correct |
45 | Correct | 352 ms | 23620 KB | Output is correct |
46 | Incorrect | 179 ms | 21748 KB | Output isn't correct |
47 | Incorrect | 145 ms | 22332 KB | Output isn't correct |
48 | Incorrect | 159 ms | 24204 KB | Output isn't correct |
49 | Correct | 114 ms | 19132 KB | Output is correct |
50 | Correct | 107 ms | 19192 KB | Output is correct |
51 | Correct | 125 ms | 19296 KB | Output is correct |
52 | Correct | 111 ms | 18868 KB | Output is correct |
53 | Correct | 335 ms | 24212 KB | Output is correct |
54 | Incorrect | 139 ms | 21304 KB | Output isn't correct |