Submission #631479

#TimeUsernameProblemLanguageResultExecution timeMemory
631479bachhoangxuanPipes (BOI13_pipes)C++17
41.48 / 100
202 ms14644 KiB
#include<bits/stdc++.h> using namespace std; #define maxn 100005 #define pii pair<int,int> vector<pii> edge[maxn]; int n,m,c[maxn],st,num=0,ans[maxn]; bool check[maxn],visited[maxn]; bool dfs(int u,int par){ bool ok=false;visited[u]=true; for(pii x:edge[u]){ int v=x.first; if(v==par) continue; if(visited[v]){st=v;ok=true;} else if(dfs(v,u)) ok=true; } if(ok){check[u]=true;num++;} if(st==u){st=0;return false;} if(ok) return true; return false; } void dfs2(int u,int par){ for(pii v:edge[u]){ if(v.first==par || check[v.first]) continue; dfs2(v.first,u); ans[v.second]=c[v.first]; c[u]+=c[v.first]; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); cin >> n >> m; if(m>n){ cout << 0 << '\n'; return 0; } for(int i=1;i<=n;i++) cin >> c[i]; for(int i=1;i<=m;i++){ int u,v;cin >> u >> v; edge[u].push_back({v,i}); edge[v].push_back({u,i}); } dfs(1,0); if(num%2==0 && m==n){ cout << 0 << '\n'; return 0; } for(int i=1;i<=n;i++){ if(check[i]) dfs2(i,0); } if(m!=n) dfs2(1,0); int cur=0,u=0; for(int i=1;i<=n;i++){ if(check[i]){cur=i;u=i;break;} } while(true){ for(pii v:edge[u]){ if(check[v.first]){ ans[v.second]=c[u]; c[v.first]+=c[u]; u=v.first; break; } } if(u==cur) break; } for(int i=1;i<=m;i++) cout << ans[i]*2 << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...