# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
199450 | 2020-02-01T12:51:03 Z | TadijaSebez | Pipes (BOI13_pipes) | C++11 | 1000 ms | 80608 KB |
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back const int N=100050; const int M=500050; int deg[N]; ll c[N],ans[M]; vector<pair<int,int>> E[N]; bool was[N],vis[N],cyc[N]; int dep[N],mnd[N],par[N]; void No(){printf("0\n");exit(0);} void DFS(int u,int p=0){ vis[u]=1; for(auto e:E[u]){ int v=e.first; if(!vis[v]){ dep[v]=dep[u]+1; par[v]=u; DFS(v,u); }else if(dep[v]<dep[u] && v!=p){ //printf("%i %i %i\n",dep[u]-dep[v],u,v); if((dep[u]-dep[v])%2==1)No(); for(int w=u;w!=v;w=par[w]){ if(cyc[w])No(); cyc[w]=1; } } } } int main(){ int n,m; scanf("%i %i",&n,&m); for(int i=1;i<=n;i++)scanf("%lld",&c[i]); map<pair<int,int>,int> idx; for(int i=1,u,v;i<=m;i++)scanf("%i %i",&u,&v),E[u].pb({v,i}),E[v].pb({u,i}),deg[u]++,deg[v]++,idx[{u,v}]=idx[{v,u}]=i; DFS(1); queue<int> q; for(int i=1;i<=n;i++)if(deg[i]==1)q.push(i); while(q.size()){ int x=q.front(); q.pop(); was[x]=1; for(auto e:E[x])if(!was[e.first]){ int y,i;tie(y,i)=e; deg[y]--; ans[i]=c[x]*2; c[y]-=c[x]; c[x]=0; if(deg[y]==1)q.push(y); } } if(n!=m){ for(int i=1;i<=n;i++)if(c[i]!=0)return 0*printf("0\n"); for(int i=1;i<=m;i++)printf("%lld\n",ans[i]); }else{ int u=-1; for(int i=1;i<=n;i++)if(!was[i])u=i; vector<int> cycle; function<void(int)> DFS1=[&](int u){ was[u]=1; cycle.pb(u); for(auto e:E[u]){ int v,i;tie(v,i)=e; if(!was[v]){ //printf("add:%i %i %i\n",u,v,c[u]*2); ans[i]+=c[u]*2; c[v]-=c[u]; c[u]=0; DFS1(v); } } }; DFS1(u); int v=-1; for(int i:cycle)if(c[i]!=0)v=i; //printf("v:%i %i\n",v,c[v]); int flu=c[v]; int j; for(int i=0;i<cycle.size();i++)if(cycle[i]==v)j=i; for(int i=0;i<cycle.size();i++){ int f=cycle[(j+i)%cycle.size()],s=cycle[(j+i+1)%cycle.size()]; ans[idx[{f,s}]]+=flu; //printf("add:%i %i %i\n",f,s,flu); flu=-flu; } for(int i=1;i<=m;i++)printf("%lld\n",ans[i]); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 2680 KB | Output is correct |
2 | Correct | 7 ms | 2732 KB | Output is correct |
3 | Correct | 9 ms | 2936 KB | Output is correct |
4 | Correct | 316 ms | 24000 KB | Output is correct |
5 | Correct | 6 ms | 2680 KB | Output is correct |
6 | Correct | 7 ms | 2680 KB | Output is correct |
7 | Correct | 7 ms | 2680 KB | Output is correct |
8 | Correct | 6 ms | 2684 KB | Output is correct |
9 | Correct | 10 ms | 2936 KB | Output is correct |
10 | Correct | 9 ms | 2936 KB | Output is correct |
11 | Correct | 8 ms | 2936 KB | Output is correct |
12 | Correct | 8 ms | 2936 KB | Output is correct |
13 | Correct | 191 ms | 19768 KB | Output is correct |
14 | Correct | 313 ms | 23044 KB | Output is correct |
15 | Correct | 329 ms | 24152 KB | Output is correct |
16 | Correct | 289 ms | 20856 KB | Output is correct |
17 | Correct | 285 ms | 24092 KB | Output is correct |
18 | Correct | 329 ms | 24152 KB | Output is correct |
19 | Correct | 333 ms | 26616 KB | Output is correct |
20 | Correct | 9 ms | 2680 KB | Output is correct |
21 | Correct | 7 ms | 2936 KB | Output is correct |
22 | Correct | 295 ms | 24084 KB | Output is correct |
23 | Correct | 227 ms | 19704 KB | Output is correct |
24 | Correct | 320 ms | 24148 KB | Output is correct |
25 | Correct | 241 ms | 20576 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 2680 KB | Output is correct |
2 | Correct | 8 ms | 2936 KB | Output is correct |
3 | Correct | 217 ms | 23980 KB | Output is correct |
4 | Correct | 284 ms | 27896 KB | Output is correct |
5 | Correct | 283 ms | 23136 KB | Output is correct |
6 | Execution timed out | 1065 ms | 78264 KB | Time limit exceeded |
7 | Correct | 7 ms | 2680 KB | Output is correct |
8 | Correct | 9 ms | 2680 KB | Output is correct |
9 | Correct | 7 ms | 2680 KB | Output is correct |
10 | Correct | 7 ms | 2680 KB | Output is correct |
11 | Correct | 7 ms | 2680 KB | Output is correct |
12 | Correct | 7 ms | 2680 KB | Output is correct |
13 | Correct | 7 ms | 2808 KB | Output is correct |
14 | Correct | 7 ms | 2680 KB | Output is correct |
15 | Correct | 8 ms | 2936 KB | Output is correct |
16 | Correct | 7 ms | 2940 KB | Output is correct |
17 | Correct | 8 ms | 2936 KB | Output is correct |
18 | Correct | 8 ms | 2936 KB | Output is correct |
19 | Correct | 8 ms | 2936 KB | Output is correct |
20 | Correct | 8 ms | 2936 KB | Output is correct |
21 | Correct | 10 ms | 3192 KB | Output is correct |
22 | Correct | 9 ms | 2936 KB | Output is correct |
23 | Correct | 265 ms | 23448 KB | Output is correct |
24 | Correct | 371 ms | 27416 KB | Output is correct |
25 | Correct | 238 ms | 24056 KB | Output is correct |
26 | Correct | 236 ms | 27256 KB | Output is correct |
27 | Correct | 260 ms | 27576 KB | Output is correct |
28 | Correct | 298 ms | 24312 KB | Output is correct |
29 | Correct | 998 ms | 71920 KB | Output is correct |
30 | Correct | 342 ms | 28928 KB | Output is correct |
31 | Correct | 368 ms | 29580 KB | Output is correct |
32 | Correct | 312 ms | 25332 KB | Output is correct |
33 | Correct | 240 ms | 25772 KB | Output is correct |
34 | Correct | 279 ms | 26744 KB | Output is correct |
35 | Correct | 236 ms | 27896 KB | Output is correct |
36 | Correct | 281 ms | 23800 KB | Output is correct |
37 | Execution timed out | 1054 ms | 80608 KB | Time limit exceeded |
38 | Correct | 342 ms | 28552 KB | Output is correct |
39 | Correct | 254 ms | 24568 KB | Output is correct |
40 | Correct | 348 ms | 27140 KB | Output is correct |
41 | Correct | 240 ms | 27512 KB | Output is correct |
42 | Correct | 265 ms | 27000 KB | Output is correct |
43 | Correct | 259 ms | 28156 KB | Output is correct |
44 | Correct | 243 ms | 23264 KB | Output is correct |
45 | Execution timed out | 1051 ms | 77372 KB | Time limit exceeded |
46 | Correct | 355 ms | 29684 KB | Output is correct |
47 | Correct | 341 ms | 27124 KB | Output is correct |
48 | Correct | 398 ms | 29168 KB | Output is correct |
49 | Correct | 243 ms | 22264 KB | Output is correct |
50 | Correct | 283 ms | 26744 KB | Output is correct |
51 | Correct | 281 ms | 25464 KB | Output is correct |
52 | Correct | 269 ms | 24336 KB | Output is correct |
53 | Execution timed out | 1018 ms | 74376 KB | Time limit exceeded |
54 | Execution timed out | 121 ms | 15660 KB | Time limit exceeded (wall clock) |