Submission #225269

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
225269	2020-04-20T05:58:28 Z	kshitij_sodani	Pipes (BOI13_pipes)	C++17	100 / 100	501 ms	74772 KB

pipes

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
typedef long long llo;
#define a first
#define b second
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	llo n,m;
	cin>>n>>m;
	llo it[n];
	set<pair<llo,llo>> adj[n];
	for(llo i=0;i<n;i++){
		cin>>it[i];
	}
	llo aa,bb;
	queue<llo> st;
	for(llo i=0;i<m;i++){
		cin>>aa>>bb;
		adj[aa-1].insert({bb-1,i});
		adj[bb-1].insert({aa-1,i});
	}
	if(m>n){
		cout<<0<<endl;
		return 0;
	}
	for(llo i=0;i<n;i++){
		if(adj[i].size()==1){
			st.push(i);
		}
	}
	llo ans[m];
	llo tot=n;
	llo vis[n];
	for(llo i=0;i<n;i++){
		vis[i]=0;
	
	}
	while(st.size()){
		llo x=st.front();
		st.pop();
		vis[x]=1;
		tot-=1;
		for(auto jj:adj[x]){
			adj[jj.a].erase({x,jj.b});
			ans[jj.b]=2*it[x];
			it[jj.a]-=it[x];
			if(adj[jj.a].size()==1){
				st.push(jj.a);
			}
		}
		adj[x].clear();
	}
	if(m==n-1){
		for(llo i=0;i<m;i++){
			cout<<ans[i]<<endl;
		}
		return 0;
	}

	if(tot%2==0){
		cout<<0<<endl;
	}
	else{

		llo ind=0;
		for(llo i=0;i<n;i++){
			if(vis[i]==0){
				ind=i;
				break;
			}
		}
		vector<pair<llo,llo>> p;
		p.pb({ind,(llo)-1});
		for(llo i=0;i<tot;i++){
			for(auto nn:adj[p[p.size()-1].a]){
				if(p.size()>1){
					if(nn.a==p[p.size()-2].a){
						continue;
					}
				}
		
				p.pb({nn.a,(llo)-1});
				p[p.size()-2].b=nn.b;
				break;
			}
		}
	
		llo su=0;
		for(llo i=0;i<tot;i++){
			if(i==0){
				su+=it[p[i].a];
				continue;
			}
			if(i%2==1){
				su+=it[p[i].a];
			}
			else{
				su-=it[p[i].a];
			}
		}

		for(llo i=0;i<tot;i++){
			if(i>0){
				ans[p[i].b]=2*(it[p[i].a]-ans[p[i-1].b]/2);
			}
			if(i==0){
				ans[p[i].b]=su;
			}
		}
		for(llo i=0;i<m;i++){
			cout<<ans[i]<<endl;
		}
	}



	return 0;
}	

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	7 ms	640 KB	Output is correct
4	Correct	322 ms	22060 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	7 ms	512 KB	Output is correct
10	Correct	7 ms	512 KB	Output is correct
11	Correct	7 ms	512 KB	Output is correct
12	Correct	7 ms	512 KB	Output is correct
13	Correct	252 ms	17784 KB	Output is correct
14	Correct	312 ms	21084 KB	Output is correct
15	Correct	313 ms	22200 KB	Output is correct
16	Correct	267 ms	18936 KB	Output is correct
17	Correct	323 ms	22076 KB	Output is correct
18	Correct	317 ms	22204 KB	Output is correct
19	Correct	314 ms	22008 KB	Output is correct
20	Correct	5 ms	384 KB	Output is correct
21	Correct	7 ms	512 KB	Output is correct
22	Correct	317 ms	22068 KB	Output is correct
23	Correct	264 ms	17888 KB	Output is correct
24	Correct	309 ms	22200 KB	Output is correct
25	Correct	264 ms	18700 KB	Output is correct

Subtask #2

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	7 ms	640 KB	Output is correct
3	Correct	98 ms	20472 KB	Output is correct
4	Correct	77 ms	19960 KB	Output is correct
5	Correct	79 ms	19448 KB	Output is correct
6	Correct	501 ms	74772 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	5 ms	384 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct
15	Correct	7 ms	640 KB	Output is correct
16	Correct	7 ms	512 KB	Output is correct
17	Correct	5 ms	512 KB	Output is correct
18	Correct	5 ms	512 KB	Output is correct
19	Correct	5 ms	512 KB	Output is correct
20	Correct	5 ms	512 KB	Output is correct
21	Correct	6 ms	768 KB	Output is correct
22	Correct	7 ms	512 KB	Output is correct
23	Correct	253 ms	19048 KB	Output is correct
24	Correct	300 ms	23020 KB	Output is correct
25	Correct	100 ms	20472 KB	Output is correct
26	Correct	81 ms	20088 KB	Output is correct
27	Correct	84 ms	19792 KB	Output is correct
28	Correct	83 ms	20600 KB	Output is correct
29	Correct	394 ms	61048 KB	Output is correct
30	Correct	296 ms	22432 KB	Output is correct
31	Correct	294 ms	23660 KB	Output is correct
32	Correct	310 ms	22772 KB	Output is correct
33	Correct	99 ms	21752 KB	Output is correct
34	Correct	78 ms	19960 KB	Output is correct
35	Correct	77 ms	19960 KB	Output is correct
36	Correct	80 ms	20088 KB	Output is correct
37	Correct	490 ms	74740 KB	Output is correct
38	Correct	285 ms	22796 KB	Output is correct
39	Correct	298 ms	22380 KB	Output is correct
40	Correct	292 ms	22892 KB	Output is correct
41	Correct	88 ms	21496 KB	Output is correct
42	Correct	79 ms	19960 KB	Output is correct
43	Correct	77 ms	19964 KB	Output is correct
44	Correct	77 ms	19448 KB	Output is correct
45	Correct	476 ms	64120 KB	Output is correct
46	Correct	302 ms	22640 KB	Output is correct
47	Correct	308 ms	22984 KB	Output is correct
48	Correct	300 ms	23696 KB	Output is correct
49	Correct	117 ms	20600 KB	Output is correct
50	Correct	77 ms	19836 KB	Output is correct
51	Correct	82 ms	19936 KB	Output is correct
52	Correct	76 ms	19580 KB	Output is correct
53	Correct	446 ms	66168 KB	Output is correct
54	Correct	309 ms	22548 KB	Output is correct