oj.uz

Submission #107061

# Submission time Handle Problem Language Result Execution time Memory
107061 2019-04-21T16:09:30 Z Pajaraja Pipes (BOI13_pipes) C++17
74.0741 / 100
 363 ms 24692 KB 
#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;}
		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+1]-parc[i]);
		mp[make_pair(c[0],c[c.size()-1])]=mp[make_pair(c[c.size()-1],c[0])]=2*(tz-parc[c.size()-1]);
	}
	for(int i=0;i<m;i++) printf("%lld\n",mp[make_pair(gr[i][0],gr[i][1])]);
}

Compilation message

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:49: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:51: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:53: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:54: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+1]-parc[i]);
               ~^~~~~~~~~~~
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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 7 ms 2944 KB Output is correct
4 Correct 362 ms 21240 KB Output is correct
5 Correct 5 ms 2688 KB Output is correct
6 Correct 4 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 4 ms 2688 KB Output is correct
9 Correct 6 ms 2944 KB Output is correct
10 Correct 5 ms 2816 KB Output is correct
11 Correct 7 ms 2844 KB Output is correct
12 Correct 6 ms 2816 KB Output is correct
13 Correct 265 ms 17316 KB Output is correct
14 Correct 328 ms 20084 KB Output is correct
15 Correct 348 ms 21112 KB Output is correct
16 Correct 323 ms 18252 KB Output is correct
17 Correct 330 ms 20984 KB Output is correct
18 Correct 324 ms 21112 KB Output is correct
19 Correct 281 ms 20956 KB Output is correct
20 Correct 4 ms 2688 KB Output is correct
21 Correct 5 ms 2944 KB Output is correct
22 Correct 318 ms 21112 KB Output is correct
23 Correct 284 ms 17216 KB Output is correct
24 Correct 363 ms 21088 KB Output is correct
25 Correct 290 ms 18116 KB Output is correct

Subtask #2
44.0740740741 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2688 KB Output isn't correct
2 Incorrect 6 ms 2944 KB Output isn't correct
3 Correct 181 ms 15704 KB Output is correct
4 Correct 115 ms 10740 KB Output is correct
5 Correct 224 ms 16628 KB Output is correct
6 Correct 336 ms 15864 KB Output is correct
7 Incorrect 4 ms 2688 KB Output isn't correct
8 Incorrect 4 ms 2688 KB Output isn't correct
9 Correct 3 ms 2688 KB Output is correct
10 Correct 5 ms 2688 KB Output is correct
11 Correct 5 ms 2816 KB Output is correct
12 Correct 4 ms 2688 KB Output is correct
13 Correct 4 ms 2688 KB Output is correct
14 Incorrect 5 ms 2688 KB Output isn't correct
15 Incorrect 7 ms 2944 KB Output isn't correct
16 Incorrect 6 ms 2844 KB Output isn't correct
17 Correct 6 ms 2816 KB Output is correct
18 Correct 5 ms 2816 KB Output is correct
19 Correct 5 ms 2816 KB Output is correct
20 Correct 6 ms 2816 KB Output is correct
21 Correct 5 ms 2816 KB Output is correct
22 Incorrect 5 ms 2816 KB Output isn't correct
23 Incorrect 251 ms 19956 KB Output isn't correct
24 Incorrect 326 ms 23308 KB Output isn't correct
25 Correct 173 ms 15732 KB Output is correct
26 Correct 129 ms 11700 KB Output is correct
27 Correct 76 ms 9104 KB Output is correct
28 Correct 193 ms 15128 KB Output is correct
29 Correct 259 ms 13868 KB Output is correct
30 Incorrect 344 ms 22520 KB Output isn't correct
31 Incorrect 309 ms 24692 KB Output isn't correct
32 Incorrect 338 ms 21740 KB Output isn't correct
33 Correct 190 ms 15724 KB Output is correct
34 Correct 139 ms 10520 KB Output is correct
35 Correct 122 ms 10800 KB Output is correct
36 Correct 171 ms 15764 KB Output is correct
37 Correct 275 ms 15836 KB Output is correct
38 Incorrect 292 ms 22956 KB Output isn't correct
39 Incorrect 336 ms 21396 KB Output isn't correct
40 Incorrect 313 ms 23068 KB Output isn't correct
41 Correct 142 ms 12788 KB Output is correct
42 Correct 80 ms 8280 KB Output is correct
43 Correct 79 ms 8280 KB Output is correct
44 Correct 206 ms 16760 KB Output is correct
45 Correct 255 ms 13532 KB Output is correct
46 Incorrect 326 ms 22772 KB Output isn't correct
47 Incorrect 356 ms 23224 KB Output isn't correct
48 Incorrect 310 ms 24556 KB Output isn't correct
49 Correct 243 ms 18336 KB Output is correct
50 Correct 140 ms 12524 KB Output is correct
51 Correct 179 ms 14460 KB Output is correct
52 Correct 112 ms 10680 KB Output is correct
53 Correct 258 ms 13816 KB Output is correct
54 Incorrect 327 ms 22576 KB Output isn't correct