| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 633107 |
2022-08-21T15:50:47 Z |
anhduc2701 |
Pipes (BOI13_pipes) |
C++17 |
|
137 ms |
18488 KB |
#include<bits/stdc++.h>
using namespace std;
int n,m;
long long a[100005],par[100005],H[100005],ans[100005];
bool vis[100005];
long long c[2];
vector<pair<int,int>>Edge;
vector<pair<int,int>>G[100005];
void DFS(int u,int p=-1){
for(auto v:G[u]){
if(v.first==p)continue;
if(H[v.first]!=-1){
if((H[u]-H[v.first])%2==1){
cout<<0;
exit(0);
}
}
else{
H[v.first]=H[u]+1;
DFS(v.first,u);
}
}
}
void DFS2(int u,int p=-1){
vis[u]=1;
for(auto v:G[u]){
if(vis[v.first])continue;
DFS2(v.first,u);
ans[v.second]=a[v.first];
a[u]-=a[v.first];
}
}
int main(){
cin>>n>>m;
if(n<m){
cout<<0;
return 0;
}
for(int i=1;i<=n;i++){
H[i]=-1;
cin>>a[i];
}
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
G[u].push_back({v,i-1});
G[v].push_back({u,i-1});
Edge.push_back({u,v});
}
H[1]=0;
DFS(1);
for(int i=1;i<=n;i++){
c[H[i]%2]+=a[i];
}
for(int i=0;i<m;i++){
pair<int,int>x=Edge[i];
if(H[x.first]%2==H[x.second]%2){
if(H[x.first]%2==1){
ans[i]=(c[i]-c[0])/2;
a[x.first]-=ans[i];
a[x.second]-=ans[i];
}
else{
ans[i]=(c[0]-c[1])/2;
a[x.first]-=ans[i];
a[x.second]-=ans[i];
}
}
}
DFS2(1);
for(int i=0;i<m;i++){
cout<<ans[i]*2<<'\n';
}
}
// 0->1 ->2 ->3 ->4 ->5->6->2
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
2660 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2772 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 4 |
Correct |
129 ms |
11492 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2656 KB |
Output is correct |
| 6 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 7 |
Correct |
2 ms |
2660 KB |
Output is correct |
| 8 |
Correct |
2 ms |
2664 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 11 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 12 |
Correct |
3 ms |
2796 KB |
Output is correct |
| 13 |
Correct |
96 ms |
9772 KB |
Output is correct |
| 14 |
Correct |
127 ms |
11052 KB |
Output is correct |
| 15 |
Correct |
129 ms |
11556 KB |
Output is correct |
| 16 |
Correct |
94 ms |
10240 KB |
Output is correct |
| 17 |
Correct |
107 ms |
11512 KB |
Output is correct |
| 18 |
Correct |
121 ms |
11636 KB |
Output is correct |
| 19 |
Correct |
134 ms |
14820 KB |
Output is correct |
| 20 |
Correct |
2 ms |
2676 KB |
Output is correct |
| 21 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 22 |
Correct |
113 ms |
11616 KB |
Output is correct |
| 23 |
Correct |
101 ms |
9656 KB |
Output is correct |
| 24 |
Correct |
117 ms |
11584 KB |
Output is correct |
| 25 |
Correct |
94 ms |
10048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2644 KB |
Output isn't correct |
| 2 |
Correct |
3 ms |
2796 KB |
Output is correct |
| 3 |
Correct |
101 ms |
12392 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 5 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 7 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
| 8 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 9 |
Correct |
2 ms |
2656 KB |
Output is correct |
| 10 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 11 |
Correct |
2 ms |
2656 KB |
Output is correct |
| 12 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 13 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 14 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 15 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 16 |
Correct |
2 ms |
2664 KB |
Output is correct |
| 17 |
Correct |
3 ms |
2664 KB |
Output is correct |
| 18 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 19 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 20 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 21 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 22 |
Correct |
2 ms |
2796 KB |
Output is correct |
| 23 |
Correct |
105 ms |
13608 KB |
Output is correct |
| 24 |
Correct |
131 ms |
15416 KB |
Output is correct |
| 25 |
Correct |
87 ms |
12292 KB |
Output is correct |
| 26 |
Correct |
1 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 |
1 ms |
2644 KB |
Output is correct |
| 30 |
Incorrect |
128 ms |
17772 KB |
Output isn't correct |
| 31 |
Correct |
123 ms |
17904 KB |
Output is correct |
| 32 |
Correct |
137 ms |
12792 KB |
Output is correct |
| 33 |
Correct |
102 ms |
13428 KB |
Output is correct |
| 34 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 35 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 36 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 37 |
Correct |
2 ms |
2664 KB |
Output is correct |
| 38 |
Correct |
122 ms |
16888 KB |
Output is correct |
| 39 |
Correct |
109 ms |
12260 KB |
Output is correct |
| 40 |
Incorrect |
119 ms |
15140 KB |
Output isn't correct |
| 41 |
Correct |
133 ms |
15132 KB |
Output is correct |
| 42 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 43 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 44 |
Correct |
1 ms |
2644 KB |
Output is correct |
| 45 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 46 |
Correct |
119 ms |
18488 KB |
Output is correct |
| 47 |
Incorrect |
123 ms |
15192 KB |
Output isn't correct |
| 48 |
Correct |
129 ms |
17600 KB |
Output is correct |
| 49 |
Correct |
102 ms |
10740 KB |
Output is correct |
| 50 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 51 |
Correct |
3 ms |
2644 KB |
Output is correct |
| 52 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 53 |
Correct |
2 ms |
2644 KB |
Output is correct |
| 54 |
Correct |
120 ms |
16240 KB |
Output is correct |
