Submission #673504

#TimeUsernameProblemLanguageResultExecution timeMemory
673504LoboPipes (BOI13_pipes)C++17
100 / 100
190 ms51312 KiB
#include<bits/stdc++.h> using namespace std; const long long inf = (long long) 1e18 + 10; const int inf1 = (int) 1e9 + 10; #define int long long #define dbl long double #define endl '\n' #define sc second #define fr first #define mp make_pair #define pb push_back #define all(x) x.begin(), x.end() const int maxn = 5e5+10; int n, m, c[maxn], ans[maxn], gr[maxn]; vector<pair<int,int>> g[maxn], g1[maxn]; int sm = 0; vector<int> vrt; void dfs(int u, int ant, int cnt) { sm+= c[u]*cnt; auto V = g1[u][0]; if(V.fr == ant) V = g1[u][1]; int v = V.fr; if(v == vrt[0]) return; dfs(v,u,cnt*-1); } void solve() { cin >> n >> m; for(int i = 1; i <= n; i++) { cin >> c[i]; } for(int i = 1; i <= m; i++) { int u,v; cin >> u >> v; g[u].pb(mp(v,i)); g[v].pb(mp(u,i)); gr[u]++; gr[v]++; } if(m > n) { cout << 0 << endl; return; } queue<int> q; for(int i = 1; i <= n; i++) { if(gr[i] == 1) q.push(i); } while(q.size()) { int u = q.front(); q.pop(); gr[u] = -1; for(auto V : g[u]) { int v = V.fr; int id = V.sc; if(gr[v] == -1) continue; ans[id] = 2*c[u]; c[v]-= c[u]; if(--gr[v] == 1) q.push(v); } } if(n == m) { for(int i = 1; i <= n; i++) { if(gr[i] != -1) { vrt.pb(i); for(auto V : g[i]) { if(gr[V.fr] != -1) { g1[i].pb(V); } } } } if(vrt.size()%2 == 1) { dfs(vrt[0],-1,1); ans[g1[vrt[0]][1].sc] = sm; c[g1[vrt[0]][1].fr]-= sm/2; c[vrt[0]]-= sm/2; gr[g1[vrt[0]][1].fr]--; gr[vrt[0]]--; q.push(g1[vrt[0]][1].fr); q.push(vrt[0]); } else { cout << 0 << endl; return; } while(q.size()) { int u = q.front(); q.pop(); gr[u] = -1; for(auto V : g[u]) { int v = V.fr; int id = V.sc; if(gr[v] == -1 || id == g1[vrt[0]][1].sc) continue; ans[id] = 2*c[u]; c[v]-= c[u]; if(--gr[v] == 1) q.push(v); } } } for(int i = 1; i <= m; i++) { cout << ans[i] << endl; } } int32_t main() { ios::sync_with_stdio(false); cin.tie(0); // freopen("in.in", "r", stdin); // freopen("out.out", "w", stdout); int tt = 1; // cin >> tt; while(tt--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...