Submission #207269

#TimeUsernameProblemLanguageResultExecution timeMemory
207269MvCPipes (BOI13_pipes)C++11
70 / 100
112 ms19396 KiB
#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #define rc(x) return cout<<x<<endl,0 #define pb push_back #define mkp make_pair #define in insert #define er erase #define fd find #define fr first #define sc second typedef long long ll; typedef long double ld; const ll INF=0x3f3f3f3f3f3f3f3f; const ll llinf=(1LL<<62); const int inf=(1<<30); const int nmax=5e5+50; const int mod=1e9+7; using namespace std; int n,m,i,ex[nmax],ey[nmax],deg[nmax],vl[nmax],vl1[nmax],rs[nmax],viz[nmax],g[nmax],cur,x,y,st; vector<int>vc,a[nmax]; queue<int>q; int main() { //freopen("sol.in","r",stdin); //freopen("sol.out","w",stdout); //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0); cin>>n>>m; if(m>n)rc(0); for(i=1;i<=n;i++)cin>>g[i]; for(i=1;i<=m;i++) { cin>>ex[i]>>ey[i]; a[ex[i]].pb(i); a[ey[i]].pb(i); } for(i=1;i<=n;i++) { deg[i]=(int)a[i].size(); if(deg[i]==1)q.push(i),viz[i]=1; } while(!q.empty()) { x=q.front(); q.pop(); for(i=0;i<(int)a[x].size();i++) { y=ex[a[x][i]]^ey[a[x][i]]^x; if(!deg[y])continue; rs[a[x][i]]=2*(g[x]-vl[x]); vl[y]+=g[x]-vl[x]; vl[x]=g[x]; deg[y]--; deg[x]--; if(deg[y]==1) { viz[y]=1; q.push(y); } } } x=0; for(i=1;i<=n;i++)if(deg[i])x=i; st=x; while(1) { viz[x]=1; for(i=0;i<(int)a[x].size();i++) { y=ex[a[x][i]]^ey[a[x][i]]^x; if((!deg[y] || viz[y]) && y!=st)continue; vc.pb(a[x][i]); x=y; break; } if(st==x)break; } if((int)vc.size()%2==0)rc(0); for(i=1;i<=n;i++)vl1[i]=vl[i]; x=st; for(i=0;i<(int)vc.size();i++) { y=ex[vc[i]]^ey[vc[i]]^x; vl1[y]+=g[x]-vl1[x]; vl1[x]=g[x]; x=y; } cur=(g[x]-vl1[x])/2; x=st; for(i=0;i<(int)vc.size();i++) { y=ex[vc[i]]^ey[vc[i]]^x; cur+=g[x]-vl[x]; vl[y]+=cur; vl[x]+=cur; rs[vc[i]]=2*cur; cur=0; x=y; } for(i=1;i<=m;i++)cout<<rs[i]<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...