Submission #107064

#	Time	Username	Problem	Language	Result	Execution time	Memory
107064		Pajaraja	Pipes (BOI13_pipes)	C++17	100 / 100	435 ms	24560 KiB

pipes

#include <bits/stdc++.h>
#define MAXN 100007
#define MAXM 500007
using namespace std;
map<pair<int,int>,long long> mp;
vector<int> g[MAXN],c;
int gr[MAXM][2],n,m,deg[MAXN];
long long t[MAXN],parc[MAXN];
bool vi[MAXN];
void dfs(int s)
{
	c.push_back(s);
	vi[s]=true;
	for(int i=0;i<g[s].size();i++) if(!vi[g[s][i]]) dfs(g[s][i]);
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld",&t[i]);
	for(int i=0;i<m;i++) 
	{
		scanf("%d%d",&gr[i][0],&gr[i][1]);
		g[gr[i][0]].push_back(gr[i][1]);
		g[gr[i][1]].push_back(gr[i][0]);
	}
	queue<int> q;
	for(int i=1;i<=n;i++) deg[i]=g[i].size();
	for(int i=1;i<=n;i++) if(deg[i]==1) q.push(i);
	while(!q.empty())
	{
		int u=q.front(); q.pop();
		vi[u]=true;
		for(int i=0;i<g[u].size();i++) if(!vi[g[u][i]]) 
		{	
			deg[g[u][i]]--;
			t[g[u][i]]-=t[u];
			mp[make_pair(u,g[u][i])]=mp[make_pair(g[u][i],u)]=2*t[u];
			if(deg[g[u][i]]==1) q.push(g[u][i]);
		}
	}
	for(int i=1;i<=n;i++) if(deg[i]>2) {printf("0"); return 0;}
	for(int i=1;i<=n;i++) if(!vi[i])
	{
		c.clear();
		dfs(i);
		if(c.size()%2==0) {printf("0"); return 0;}
		if(c.size()==1) continue;
		long long tz=0;
		for(int i=0;i<c.size();i++) tz+=t[c[i]];
		tz/=2;
		for(int i=2;i<c.size();i+=2) parc[i]=parc[i-2]+t[c[i-2]];
		parc[1]=parc[c.size()-1]+t[c[c.size()-1]]-tz;
		for(int i=3;i<=c.size();i+=2) parc[i]=parc[i-2]+t[c[i-2]];
		for(int i=0;i<c.size()-1;i++) mp[make_pair(c[i],c[i+1])]=mp[make_pair(c[i+1],c[i])]=2*(parc[i+2]-parc[i+1]);
		mp[make_pair(c[c.size()-1],c[c.size()-2])]=mp[make_pair(c[c.size()-2],c[c.size()-1])]=2*(tz-parc[c.size()-1]);
		mp[make_pair(c[c.size()-1],c[0])]=mp[make_pair(c[0],c[c.size()-1])]=2*(parc[1]);
	}
	for(int i=0;i<m;i++) printf("%lld\n",mp[make_pair(gr[i][0],gr[i][1])]);
}

Compilation message (stderr)

pipes.cpp: In function 'void dfs(int)':
pipes.cpp:14:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[s].size();i++) if(!vi[g[s][i]]) dfs(g[s][i]);
              ~^~~~~~~~~~~~
pipes.cpp: In function 'int main()':
pipes.cpp:34:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[u].size();i++) if(!vi[g[u][i]]) 
               ~^~~~~~~~~~~~
pipes.cpp:50:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<c.size();i++) tz+=t[c[i]];
               ~^~~~~~~~~
pipes.cpp:52:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=2;i<c.size();i+=2) parc[i]=parc[i-2]+t[c[i-2]];
               ~^~~~~~~~~
pipes.cpp:54:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=3;i<=c.size();i+=2) parc[i]=parc[i-2]+t[c[i-2]];
               ~^~~~~~~~~~
pipes.cpp:55:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<c.size()-1;i++) mp[make_pair(c[i],c[i+1])]=mp[make_pair(c[i+1],c[i])]=2*(parc[i+2]-parc[i+1]);
               ~^~~~~~~~~~~
pipes.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
pipes.cpp:20:29: 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",&t[i]);
                        ~~~~~^~~~~~~~~~~~~~
pipes.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&gr[i][0],&gr[i][1]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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