Submission #1077720

#TimeUsernameProblemLanguageResultExecution timeMemory
1077720hung_nmPipes (BOI13_pipes)C++17
65 / 100
113 ms50812 KiB
#include <bits/stdc++.h> #define pb push_back #define fi first #define se second #define pii pair<int, int> #define pipii pair<int, pair<int, int>> #define vi vector<int> #define vpi vector<pair<int, int>> #define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin); #define out(name) if(fopen(name, "w")) freopen(name, "w", stdout); #define int long long const int N = 1e6 + 5; const int mod = 1e9 + 7; using namespace std; long long n, m, c[N], ans[N]; vpi ad[N]; void dfs(int u, int p, int id = 0) { long long res = 0; for(auto [v, pos] : ad[u]) { if(v == p) continue ; dfs(v, u, pos); res += ans[pos]; } ans[id] = c[u] - res; } void sub1() { dfs(1, 0); for(int i = 1; i <= m; ++i) { cout << 2*ans[i] << "\n"; } } long long del[N], deg[N], ok[N], tmp, x, root, vis[N]; queue<int> q; void dfs2(int u, int p, int dau) { tmp += dau * c[u]; ok[u] = 1; for(auto [v, i] : ad[u]) { if(v == p or del[v]) continue ; if(ok[v] == 0) { dfs2(v, u, dau * (-1)); } else { ans[x] = tmp; root = v; vis[u] = 1; break ; } } } void dfs3(int u = root, int p = root, int pos = x) { vis[u] = 1; for(auto [v, i] : ad[u]) { if(v == p or del[v] or vis[v]) continue ; ans[i] = 2*c[u] - ans[pos]; dfs3(v, u, i); } } void sub2() { for(int i = 1; i <= n; ++i) { if(ad[i].size() == 1) { q.push(i); } deg[i] = ad[i].size(); } if( ( n - q.size() ) % 2 == 0 ) { cout << 0; return ; } while(!q.size()) { int u = q.front(); q.pop(); for(auto [v, i] : ad[u]) { if(del[v]) continue ; ans[i] = 2*c[u]; c[v] -= c[u]; deg[v]--; if(deg[v] == 1) { q.push(v); } } del[u] = 1; } long long des; for(int i = 1; i <= n; ++i) { if(del[i] == 0) { des = i; break; } } dfs2(des, des, 1); dfs3(); for(int i = 1; i <= m; ++i) { cout << ans[i] << "\n"; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0); 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; ad[u].pb({v, i}); ad[v].pb({u, i}); } if(m > n) { cout << 0; return 0; } if(m == (n-1)) { sub1(); return 0; } return 0; }

Compilation message (stderr)

pipes.cpp: In function 'void sub2()':
pipes.cpp:114:9: warning: 'des' may be used uninitialized in this function [-Wmaybe-uninitialized]
  114 |     dfs2(des, des, 1);
      |     ~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...