Submission #199450

#	Time	Username	Problem	Language	Result	Execution time	Memory
199450		TadijaSebez	Pipes (BOI13_pipes)	C++11	93.52 / 100	1065 ms	80608 KiB

pipes

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=100050;
const int M=500050;
int deg[N];
ll c[N],ans[M];
vector<pair<int,int>> E[N];
bool was[N],vis[N],cyc[N];
int dep[N],mnd[N],par[N];
void No(){printf("0\n");exit(0);}
void DFS(int u,int p=0){
	vis[u]=1;
	for(auto e:E[u]){
		int v=e.first;
		if(!vis[v]){
			dep[v]=dep[u]+1;
			par[v]=u;
			DFS(v,u);
		}else if(dep[v]<dep[u] && v!=p){
			//printf("%i %i %i\n",dep[u]-dep[v],u,v);
			if((dep[u]-dep[v])%2==1)No();
			for(int w=u;w!=v;w=par[w]){
				if(cyc[w])No();
				cyc[w]=1;
			}
		}
	}
}
int main(){
	int n,m;
	scanf("%i %i",&n,&m);
	for(int i=1;i<=n;i++)scanf("%lld",&c[i]);
	map<pair<int,int>,int> idx;
	for(int i=1,u,v;i<=m;i++)scanf("%i %i",&u,&v),E[u].pb({v,i}),E[v].pb({u,i}),deg[u]++,deg[v]++,idx[{u,v}]=idx[{v,u}]=i;
	DFS(1);
	queue<int> q;
	for(int i=1;i<=n;i++)if(deg[i]==1)q.push(i);
	while(q.size()){
		int x=q.front();
		q.pop();
		was[x]=1;
		for(auto e:E[x])if(!was[e.first]){
			int y,i;tie(y,i)=e;
			deg[y]--;
			ans[i]=c[x]*2;
			c[y]-=c[x];
			c[x]=0;
			if(deg[y]==1)q.push(y);
		}
	}
	if(n!=m){
		for(int i=1;i<=n;i++)if(c[i]!=0)return 0*printf("0\n");
		for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
	}else{
		int u=-1;
		for(int i=1;i<=n;i++)if(!was[i])u=i;
		vector<int> cycle;
		function<void(int)> DFS1=[&](int u){
			was[u]=1;
			cycle.pb(u);
			for(auto e:E[u]){
				int v,i;tie(v,i)=e;
				if(!was[v]){
					//printf("add:%i %i %i\n",u,v,c[u]*2);
					ans[i]+=c[u]*2;
					c[v]-=c[u];
					c[u]=0;
					DFS1(v);
				}
			}
		};
		DFS1(u);
		int v=-1;
		for(int i:cycle)if(c[i]!=0)v=i;
		//printf("v:%i %i\n",v,c[v]);
		int flu=c[v];
		int j;
		for(int i=0;i<cycle.size();i++)if(cycle[i]==v)j=i;
		for(int i=0;i<cycle.size();i++){
			int f=cycle[(j+i)%cycle.size()],s=cycle[(j+i+1)%cycle.size()];
			ans[idx[{f,s}]]+=flu;
			//printf("add:%i %i %i\n",f,s,flu);
			flu=-flu;
		}
		for(int i=1;i<=m;i++)printf("%lld\n",ans[i]);
	}
	return 0;
}

Compilation message (stderr)

pipes.cpp: In function 'int main()':
pipes.cpp:80:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<cycle.size();i++)if(cycle[i]==v)j=i;
               ~^~~~~~~~~~~~~
pipes.cpp:81:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<cycle.size();i++){
               ~^~~~~~~~~~~~~
pipes.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
pipes.cpp:34:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++)scanf("%lld",&c[i]);
                       ~~~~~^~~~~~~~~~~~~~
pipes.cpp:36:95: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1,u,v;i<=m;i++)scanf("%i %i",&u,&v),E[u].pb({v,i}),E[v].pb({u,i}),deg[u]++,deg[v]++,idx[{u,v}]=idx[{v,u}]=i;
                           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pipes.cpp:79:7: warning: 'j' may be used uninitialized in this function [-Wmaybe-uninitialized]
   int j;
       ^

• Subtask 1: 30 / 30
• Subtask 2: 63.51851851851852 / 70