Submission #225269

#	Time	Username	Problem	Language	Result	Execution time	Memory
225269		kshitij_sodani	Pipes (BOI13_pipes)	C++17	100 / 100	501 ms	74772 KiB

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 / 30
• Subtask 2: 70 / 70