Submission #448914

#TimeUsernameProblemLanguageResultExecution timeMemory
448914JovanBPipes (BOI13_pipes)C++17
100 / 100
264 ms23980 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const int N = 100000; const int M = 500000; ll cap[N+5]; vector <pair <int, int>> graf[N+5]; int deg[N+5]; bool bio[N+5]; ll sol[M+5]; pair <int, int> f[N+5][2]; void idi(int v, int lst, int root){ if(v == root && lst != 0) return; int was = 0; for(auto pr : graf[v]){ int c = pr.first; if(deg[c] <= 0) continue; if(v == root){ f[v][was++] = pr; } else{ if(c == lst) f[v][0] = pr; else f[v][1] = pr; } } idi(f[v][1].first, v, root); } int main(){ ios_base::sync_with_stdio(false), cin.tie(0); cout.precision(10); cout << fixed; int n, m; cin >> n >> m; for(int i=1; i<=n; i++) cin >> cap[i]; for(int i=1; i<=m; i++){ int a, b; cin >> a >> b; graf[a].push_back({b, i}); graf[b].push_back({a, i}); deg[a]++; deg[b]++; } if(m > n){ cout << "0\n"; return 0; } queue <int> q; for(int i=1; i<=n; i++){ if(deg[i] == 1){ q.push(i); } } int ost = n; while(!q.empty()){ int v = q.front(); q.pop(); ost--; bio[v] = 1; deg[v] = 0; for(auto pr : graf[v]){ int c = pr.first, ind = pr.second; if(bio[c]) continue; sol[ind] = cap[v]; cap[v] = 0; cap[c] -= sol[ind]; deg[c]--; if(deg[c] == 1){ q.push(c); } } } if(ost > 0 && ost%2 == 0){ cout << "0\n"; return 0; } if(ost > 0){ int beg = 1; for(int i=1; i<=n; i++){ if(deg[i] > 0) beg = i; } idi(beg, 0, beg); int v = f[beg][1].first; while(v != beg){ sol[f[v][1].second] = cap[v] - sol[f[v][0].second]; v = f[v][1].first; } ll dif = cap[v] - sol[f[beg][0].second]; if(dif%2){ cout << "0\n"; return 0; } sol[f[beg][1].second] = dif/2; v = f[beg][1].first; while(v != beg){ sol[f[v][1].second] = cap[v] - sol[f[v][0].second]; v = f[v][1].first; } } for(int i=1; i<=m; i++) cout << 2*sol[i] << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...