#include <algorithm>
#include <iostream>
using namespace std;
const int N = 100000;
const int M = 500000;
int aa[N], cc[N], ii[M], jj[M], ww[M], hh[M], n_, m_, *eh[N], eo[N];
void append(int i, int h) {
int o = eo[i]++;
if (!o)
eh[i] = (int *) malloc(sizeof *eh[i]);
else if (!(o & o - 1))
eh[i] = (int *) realloc(eh[i], (o << 1) * sizeof *eh[i]);
eh[i][o] = h;
}
void dfs0(int i, int c) {
if (cc[i] != -1)
return;
n_++, cc[i] = c, c ^= 1;
for (int o = 0; o < eo[i]; o++) {
int h = eh[i][o];
if (ww[h] == -1)
ww[hh[m_++] = h] = 0;
dfs0(i ^ ii[h] ^ jj[h], c);
}
}
void dfs1(int h_, int i) {
for (int o = 0; o < eo[i]; o++) {
int h = eh[i][o];
if (h != h_ && ii[h] != -1) {
int j = i ^ ii[h] ^ jj[h];
dfs1(h, j);
ww[h] = aa[j];
aa[i] -= ww[h];
aa[j] -= ww[h];
}
}
}
bool dfs2(int i, int t, int w) {
if (cc[i] == 2)
return false;
cc[i] = 2;
if (i == t)
return true;
for (int o = 0; o < eo[i]; o++) {
int h = eh[i][o], j = i ^ ii[h] ^ jj[h];
if (dfs2(j, t, -w)) {
ww[h] += w;
return true;
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
int n, m; cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> aa[i], cc[i] = -1;
for (int h = 0; h < m; h++) {
int i, j; cin >> i >> j, i--, j--;
append(ii[h] = i, h);
append(jj[h] = j, h);
ww[h] = -1;
}
for (int i = 0; i < n; i++)
if (cc[i] == -1) {
n_ = m_ = 0, dfs0(i, 0);
if (m_ > n_) {
cout << "0\n";
return 0;
}
if (m_ == n_ - 1) {
dfs1(-1, i);
if (aa[i]) {
cout << "0\n";
return 0;
}
continue;
}
int h_ = -1;
for (int z = 0; z < m_; z++) {
int h = hh[z];
if (cc[ii[h]] == cc[jj[h]]) {
h_ = h;
break;
}
}
if (h_ == -1) {
cout << "0\n";
return 0;
}
int s = ii[h_], t = jj[h_]; ii[h_] = -1;
dfs1(-1, s);
int a = aa[s];
if (a % 2) {
cout << "0\n";
return 0;
}
a /= 2;
dfs2(s, t, a);
ww[h_] += a;
}
for (int h = 0; h < m; h++)
cout << ww[h] * 2 << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |