Submission #26392

#	Time	Username	Problem	Language	Result	Execution time	Memory
26392		samir_droubi	Pipes (BOI13_pipes)	C++14	37.59 / 100	1000 ms	107952 KiB

pipes

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

set<int>tr[mxn];
int ans[mxn*5];
bool vis[mxn];

bool ok=true;
void dfs(int v)
{
	vis[v]=true;
	set<int>::iterator it=tr[v].begin();
	for(it;it!=tr[v].end();++it)
	{
		int u=*it;
		if(vis[u])ok=false;
		else dfs(u);
	}
}
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});
		tr[x].insert(y);
		tr[y].insert(x);
	}
	for(int i=1;i<=n;++i)
	{
		set<int>::iterator it=tr[i].begin();
		for(it;it!=tr[i].end();++it)
		{
			int u=*it;
			set<int>::iterator it1=tr[u].begin();
			for(it1;it1!=tr[u].end();++it1)
			{
				int w=*it1;
				if(w==i)continue;
				if(tr[i].count(w))
				{
					tr[i].clear();
					tr[w].clear();
					tr[u].clear();
				}
			}
		}
	}
	for(int i=1;i<=n;++i)
	{
		if(!vis[i])
			dfs(i);
	}
	if(!ok)
	{
		puts("0");
		return 0;
	}
	return 0;
	for(int i=1;i<=n;++i)
		if(gr[i].size()==1)q.push(i);
	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[u].erase({v,in});
		if(gr[u].size()==1)q.push(u);
		ans[in]=2*c[v];
		c[u]-=c[v];
	}
	for(int i=1;i<=m;++i)printf("%d\n",ans[i]);
	return 0;
}

Compilation message (stderr)

pipes.cpp: In function 'void dfs(int)':
pipes.cpp:18:8: warning: statement has no effect [-Wunused-value]
  for(it;it!=tr[v].end();++it)
        ^
pipes.cpp: In function 'int main()':
pipes.cpp:29:19: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
   scanf("%d",&c[i]);
                   ^
pipes.cpp:42:9: warning: statement has no effect [-Wunused-value]
   for(it;it!=tr[i].end();++it)
         ^
pipes.cpp:46:11: warning: statement has no effect [-Wunused-value]
    for(it1;it1!=tr[u].end();++it1)
           ^
pipes.cpp:27: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:29:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&c[i]);
                    ^
pipes.cpp:33: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: 0 / 30
• Subtask 2: 37.592592592592595 / 70