Submission #477111

#	Time	Username	Problem	Language	Result	Execution time	Memory
477111		Jasiekstrz	Pipes (BOI13_pipes)	C++17	100 / 100	209 ms	23092 KiB

pipes

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e5,M=5e5;
int val[N+10];
vector<pair<int,int>> e[N+10];
bool vis[N+10];
bool on_c[N+10];
vector<int> stck;
int ans[M+10];
int pref[N+10];
int ss=0;
void on_cycle(int x)
{
	vis[x]=true;
	stck.push_back(x);
	for(auto v:e[x])
	{
		if(!vis[v.fi])
			on_cycle(v.fi);
		else if(!on_c[x] && stck.size()>=2 && stck[stck.size()-2]!=v.fi)
		{
			for(size_t i=stck.size()-1;stck[i]!=v.fi;i--)
				on_c[stck[i]]=true;
			on_c[v.fi]=true;
		}
	}
	stck.pop_back();
}
void solve_trees(int x,int p)
{
	for(auto v:e[x])
	{
		if(on_c[v.fi] || v.fi==p)
			continue;
		solve_trees(v.fi,x);
		ans[v.se]=2*val[v.fi];
		val[x]-=val[v.fi];
	}
	return;
}
void get_pref(int x,int p,int p0)
{
	for(auto v:e[x])
	{
		if(!on_c[v.fi] || v.fi==p || v.fi==p0)
			continue;
		pref[v.fi]=val[v.fi]-pref[x];
		get_pref(v.fi,x,p0);
		return;
	}
	ss=pref[x];
	return;
}
void solve_cycle(int x,int p,int p0,bool sgn_x) // true -> +, false -> -
{
	for(auto v:e[x])
	{
		if(!on_c[v.fi] || v.fi==p)
			continue;
		if(v.fi==p0)
		{
			ans[v.se]=ss;
			return;
		}
		if(sgn_x)
			ans[v.se]=-ss+2*pref[x];
		else
			ans[v.se]=ss+2*pref[x];
		solve_cycle(v.fi,x,p0,!sgn_x);
		return;
	}
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>val[i];
	for(int i=1;i<=m;i++)
	{
		int a,b;
		cin>>a>>b;
		e[a].emplace_back(b,i);
		e[b].emplace_back(a,i);
	}
	if(m>n)
	{
		cout<<"0\n";
		return 0;
	}
	if(m<n)
		solve_trees(1,0);
	else
	{
		on_cycle(1);
		int cnt_c=0,cc=0;
		for(int i=1;i<=n;i++)
		{
			if(on_c[i])
			{
				solve_trees(i,0);
				cnt_c++;
				cc=i;
			}
		}
		if(cnt_c%2==0)
		{
			cout<<"0\n";
			return 0;
		}
		pref[cc]=val[cc];
		get_pref(cc,0,cc);
		solve_cycle(cc,0,cc,true);
	}
	for(int i=1;i<=m;i++)
		cout<<ans[i]<<"\n";
	return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 70 / 70