Submission #26447

#	Time	Username	Problem	Language	Result	Execution time	Memory
26447		samir_droubi	Pipes (BOI13_pipes)	C++14	100 / 100	646 ms	56308 KiB

pipes

#include <bits/stdc++.h>
using namespace std;
int n,m;
const int mxn=(1e5)+5;
set<pair<int,int> >gr[mxn];
queue<int>q;
long long c[mxn];
int ans[mxn*5];

void run()
{
	while(!q.empty())
	{
		int v=q.front();
		q.pop();
		if(gr[v].empty())continue;

		int u=gr[v].begin()->first;
		int in=gr[v].begin()->second;

		gr[v].clear();
		gr[u].erase({v,in});

		if(gr[u].size()==1)q.push(u);

		ans[in]=2*c[v];
		c[u]-=c[v];
	}
}
long long sm;
int num;
int cnt;
void dfs(int v,int pa)
{
	++num;
	if(num%2)sm+=c[v];
	else sm-=c[v];

	set<pair<int,int > >::iterator it=gr[v].begin();
	for(it;it!=gr[v].end();++it)
	{
		int u=it->first;
		int in=it->second;
		if(u==pa)continue;
		if(cnt==num)
		{
			ans[in]=sm;
			c[u]-=(sm/2);
			c[v]-=(sm/2);
			gr[u].erase({v,in});
			gr[v].erase(it);	
			q.push(v);
			return;
		}
		dfs(u,v);
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)scanf("%d",&c[i]);
	for(int i=1;i<=m;++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		gr[x].insert({y,i});
		gr[y].insert({x,i});
	}
	if(m>n)
	{
		puts("0");
		return 0;
	}

	for(int i=1;i<=n;++i)
	{
		if(gr[i].size()==1)
			q.push(i);
	}
	run();
	if(n==m)
	{
		for(int i=1;i<=n;++i)
		{
			if(gr[i].empty())continue;
			++cnt;
		}
		if(cnt%2==0)
		{
			puts("0");
			return 0;
		}
		for(int i=1;i<=n;++i)
		{
			if(gr[i].empty())continue;
			dfs(i,i);
			break;
		}
		run();
	}
	for(int i=1;i<=m;++i)
		printf("%d\n",ans[i]);
	return 0;
}

Compilation message (stderr)

pipes.cpp: In function 'void dfs(int, int)':
pipes.cpp:40:8: warning: statement has no effect [-Wunused-value]
  for(it;it!=gr[v].end();++it)
        ^
pipes.cpp: In function 'int main()':
pipes.cpp:61:39: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
  for(int i=1;i<=n;++i)scanf("%d",&c[i]);
                                       ^
pipes.cpp:60:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
                     ^
pipes.cpp:61:40: 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("%d",&c[i]);
                                        ^
pipes.cpp:65:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&x,&y);
                      ^

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