oj.uz

Submission #26392

# Submission time Handle Problem Language Result Execution time Memory
26392 2017-06-29T18:00:57 Z samir_droubi Pipes (BOI13_pipes) C++14
37.5926 / 100
 1000 ms 107952 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 14232 KB Output isn't correct
2 Incorrect 0 ms 14232 KB Output isn't correct
3 Incorrect 0 ms 14496 KB Output isn't correct
4 Incorrect 129 ms 32844 KB Output isn't correct
5 Incorrect 0 ms 14232 KB Output isn't correct
6 Incorrect 0 ms 14232 KB Output isn't correct
7 Incorrect 0 ms 14232 KB Output isn't correct
8 Incorrect 3 ms 14232 KB Output isn't correct
9 Incorrect 6 ms 14364 KB Output isn't correct
10 Incorrect 0 ms 14496 KB Output isn't correct
11 Incorrect 6 ms 14496 KB Output isn't correct
12 Incorrect 0 ms 14496 KB Output isn't correct
13 Incorrect 209 ms 29148 KB Output isn't correct
14 Incorrect 239 ms 31920 KB Output isn't correct
15 Incorrect 263 ms 32976 KB Output isn't correct
16 Incorrect 239 ms 30204 KB Output isn't correct
17 Incorrect 283 ms 32844 KB Output isn't correct
18 Incorrect 233 ms 32976 KB Output isn't correct
19 Incorrect 276 ms 34380 KB Output isn't correct
20 Incorrect 3 ms 14232 KB Output isn't correct
21 Incorrect 3 ms 14364 KB Output isn't correct
22 Incorrect 283 ms 32976 KB Output isn't correct
23 Incorrect 226 ms 29148 KB Output isn't correct
24 Incorrect 273 ms 32976 KB Output isn't correct
25 Incorrect 213 ms 29808 KB Output isn't correct

Subtask #2
37.5925925926 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 14232 KB Output isn't correct
2 Incorrect 0 ms 14496 KB Output isn't correct
3 Correct 219 ms 33180 KB Output is correct
4 Correct 246 ms 35204 KB Output is correct
5 Correct 233 ms 32580 KB Output is correct
6 Execution timed out 1000 ms 107952 KB Execution timed out
7 Incorrect 0 ms 14232 KB Output isn't correct
8 Incorrect 0 ms 14232 KB Output isn't correct
9 Correct 0 ms 14232 KB Output is correct
10 Correct 0 ms 14232 KB Output is correct
11 Correct 0 ms 14232 KB Output is correct
12 Correct 3 ms 14232 KB Output is correct
13 Correct 3 ms 14232 KB Output is correct
14 Incorrect 3 ms 14232 KB Output isn't correct
15 Incorrect 0 ms 14496 KB Output isn't correct
16 Incorrect 3 ms 14364 KB Output isn't correct
17 Correct 0 ms 14496 KB Output is correct
18 Correct 0 ms 14496 KB Output is correct
19 Correct 3 ms 14496 KB Output is correct
20 Correct 6 ms 14496 KB Output is correct
21 Correct 9 ms 14760 KB Output is correct
22 Incorrect 3 ms 14496 KB Output isn't correct
23 Incorrect 186 ms 31044 KB Output isn't correct
24 Incorrect 266 ms 34496 KB Output isn't correct
25 Correct 266 ms 33172 KB Output is correct
26 Correct 276 ms 34904 KB Output is correct
27 Correct 256 ms 35008 KB Output is correct
28 Correct 256 ms 33900 KB Output is correct
29 Execution timed out 1000 ms 91708 KB Execution timed out
30 Incorrect 226 ms 35180 KB Output isn't correct
31 Incorrect 243 ms 35580 KB Output isn't correct
32 Incorrect 283 ms 33372 KB Output isn't correct
33 Correct 279 ms 34572 KB Output is correct
34 Correct 253 ms 34644 KB Output is correct
35 Correct 276 ms 35208 KB Output is correct
36 Correct 289 ms 33240 KB Output is correct
37 Execution timed out 1000 ms 107952 KB Execution timed out
38 Incorrect 263 ms 35148 KB Output isn't correct
39 Incorrect 259 ms 33048 KB Output isn't correct
40 Incorrect 253 ms 34360 KB Output isn't correct
41 Correct 229 ms 35580 KB Output is correct
42 Correct 236 ms 34824 KB Output is correct
43 Correct 253 ms 35424 KB Output is correct
44 Correct 246 ms 32580 KB Output is correct
45 Execution timed out 1000 ms 97392 KB Execution timed out
46 Incorrect 233 ms 35836 KB Output isn't correct
47 Incorrect 273 ms 34400 KB Output isn't correct
48 Incorrect 226 ms 35476 KB Output isn't correct
49 Correct 233 ms 32232 KB Output is correct
50 Correct 236 ms 34624 KB Output is correct
51 Correct 256 ms 33836 KB Output is correct
52 Correct 233 ms 33380 KB Output is correct
53 Execution timed out 1000 ms 98976 KB Execution timed out
54 Incorrect 219 ms 34680 KB Output isn't correct