Submission #673498

#TimeUsernameProblemLanguageResultExecution timeMemory
673498LoboPipes (BOI13_pipes)C++17
65 / 100
197 ms52212 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 beg; vector<int> vrt; void dfs(int u, int ant, int cnt) { auto V = g1[u][0]; if(V.fr == ant) V = g1[u][1]; int v = V.fr; int id = V.sc; ans[id] = c[beg]*cnt; if(v == beg) 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(m == n) { 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) { for(auto x : vrt) { if(c[x]) beg = x; } dfs(beg,-1,1); } else { } } 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...