Submission #673475

#TimeUsernameProblemLanguageResultExecution timeMemory
673475LoboPipes (BOI13_pipes)C++17
30 / 100
67 ms24400 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]; void solve() { cin >> n >> m; if(m != n-1) { assert(0); cout << 0 << endl; return; } for(int i = 1; i <= n; i++) { cin >> c[i]; } if(n == 2) { cout << 2*c[1] << endl; return; } 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]++; } 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); } } 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...