#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const int N = 100000, M = 500000;
int n, m, rmv;
int sol[M], active[N], v[N], out[N];
vector<int> g[N], num[N], s;
int solve(int mode, int val, int u, int l, int a, int b){
if(a == b) return sol[a] = val/2;
for(int i = 0, w, x; i < (int)g[u].size(); i++){
w = g[u][i];
if(w == l || !active[w]) continue;
if(mode){
x = solve(0, val+v[u], w, u, a, num[u][i]);
sol[b] = x - val;
}
else{
x = solve(1, val-v[u], w, u, a, num[u][i]);
sol[b] = val - x;
}
return x;
}
return -1;
}
int main(){
cin.tie(0);
ios::sync_with_stdio(0);
cin >> n >> m;
if(m > n){
cout << "0\n";
return 0;
}
for(int i = 0; i < n; i++) cin >> v[i];
for(int i = 0, u, w; i < m; i++){
cin >> u >> w;
u--, w--;
g[u].push_back(w), g[w].push_back(u);
num[u].push_back(i), num[w].push_back(i);
}
for(int i = 0; i < n; i++) out[i] = g[i].size(), active[i] = 1;;
for(int i = 0; i < n; i++) if(out[i] == 1) s.push_back(i);
while(!s.empty()){
int u = s.back(), j = -1;
s.pop_back();
active[u] = 0, rmv++;
for(int i = 0; i < (int)g[u].size(); i++) if(active[g[u][i]]) j = i;
if(j == -1) continue;
sol[num[u][j]] = v[u];
v[g[u][j]] -= sol[num[u][j]];
if(--out[g[u][j]] == 1) s.push_back(g[u][j]);
}
if(n-rmv && !((n-rmv)%2)){
cout << "0\n";
return 0;
}
for(int i = 0, a=-1, b=-1; i < n; i++) if(active[i]){
for(int j = 0, w; j < (int)g[i].size(); j++){
w = g[i][j];
if(!active[w]) continue;
if(a==-1) a = j;
else b = j;
}
solve(0, v[i], g[i][b], i, num[i][a], num[i][b]);
break;
}
for(int i = 0; i < m; i++) cout << 2*sol[i] << "\n";
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 4 |
Correct |
139 ms |
15348 KB |
Output is correct |
| 5 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 6 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 7 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 8 |
Correct |
5 ms |
5248 KB |
Output is correct |
| 9 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 10 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 11 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 12 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 13 |
Correct |
110 ms |
13432 KB |
Output is correct |
| 14 |
Correct |
138 ms |
14832 KB |
Output is correct |
| 15 |
Correct |
143 ms |
15444 KB |
Output is correct |
| 16 |
Correct |
116 ms |
13940 KB |
Output is correct |
| 17 |
Correct |
150 ms |
15348 KB |
Output is correct |
| 18 |
Correct |
143 ms |
15480 KB |
Output is correct |
| 19 |
Correct |
150 ms |
15224 KB |
Output is correct |
| 20 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 21 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 22 |
Correct |
143 ms |
15480 KB |
Output is correct |
| 23 |
Correct |
107 ms |
13304 KB |
Output is correct |
| 24 |
Correct |
152 ms |
15480 KB |
Output is correct |
| 25 |
Correct |
117 ms |
13692 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
5 ms |
5248 KB |
Output is correct |
| 3 |
Correct |
118 ms |
14356 KB |
Output is correct |
| 4 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 5 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 6 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 7 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 8 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 9 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 10 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 11 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 12 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 13 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 14 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 15 |
Correct |
5 ms |
5248 KB |
Output is correct |
| 16 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 17 |
Correct |
6 ms |
5120 KB |
Output is correct |
| 18 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 19 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 20 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 21 |
Correct |
4 ms |
5024 KB |
Output is correct |
| 22 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 23 |
Correct |
116 ms |
15736 KB |
Output is correct |
| 24 |
Correct |
145 ms |
17656 KB |
Output is correct |
| 25 |
Correct |
114 ms |
14256 KB |
Output is correct |
| 26 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 27 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 28 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 29 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 30 |
Correct |
148 ms |
17016 KB |
Output is correct |
| 31 |
Correct |
153 ms |
19064 KB |
Output is correct |
| 32 |
Correct |
141 ms |
16116 KB |
Output is correct |
| 33 |
Correct |
126 ms |
14712 KB |
Output is correct |
| 34 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 35 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 36 |
Correct |
6 ms |
4992 KB |
Output is correct |
| 37 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 38 |
Correct |
146 ms |
17232 KB |
Output is correct |
| 39 |
Correct |
143 ms |
15860 KB |
Output is correct |
| 40 |
Correct |
148 ms |
17656 KB |
Output is correct |
| 41 |
Correct |
109 ms |
14584 KB |
Output is correct |
| 42 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 43 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 44 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 45 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 46 |
Correct |
141 ms |
16760 KB |
Output is correct |
| 47 |
Correct |
149 ms |
17528 KB |
Output is correct |
| 48 |
Correct |
149 ms |
18940 KB |
Output is correct |
| 49 |
Correct |
116 ms |
14452 KB |
Output is correct |
| 50 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 51 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 52 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 53 |
Correct |
5 ms |
4992 KB |
Output is correct |
| 54 |
Correct |
144 ms |
16632 KB |
Output is correct |
