Submission #307085

#	Time	Username	Problem	Language	Result	Execution time	Memory
307085		Rainbowbunny	Pipes (BOI13_pipes)	C++17	100 / 100	105 ms	16872 KiB

pipes

#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define eb emplace_back
#define fi first
#define se second
using namespace std;
using cd = complex <double>;
 
const long long INF = 1e15;
const int N = 3e5 + 2;
const int mod = 1e9 + 7;//998244353;//1e9 + 7;//786433;
const double Pi = acos(-1);
 
void Fastio()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}
 
int n, m;
long long a[100005], par[100005], H[100005], ans[100005];
bool Vis[100005];
long long c[2];
vector <pair <int, int> > Edge;
vector <pair <int, int> > Adj[100005];
 
void DFS(int node, int p = -1)
{
	for(auto x : Adj[node])
	{
		if(x.fi == p)
		{
			continue;
		}
		if(H[x.fi] != -1)
		{
			if((H[node] - H[x.fi]) % 2 == 1)
			{
				cout << 0;
				exit(0);
			}
		}
		else
		{
			H[x.fi] = H[node] + 1;
			DFS(x.fi, node);
		}
	}
}
 
void DFS2(int node, int p = -1)
{
	Vis[node] = true;
	for(auto x : Adj[node])
	{
		if(Vis[x.fi])
		{
			continue;
		}
		DFS2(x.fi, node);
		ans[x.se] = a[x.fi];
		a[node] -= a[x.fi]; 
	}
}
 
signed main()
{
	Fastio();
	cin >> n >> m;
	if(n < m)
	{
		cout << 0;
		return 0;
	}
	for(int i = 1; i <= n; i++)
	{
		H[i] = -1;
		cin >> a[i];
	}
	for(int i = 1; i <= m; i++)
	{
		int u, v;
		cin >> u >> v;
		Adj[u].eb(v, i - 1);
		Adj[v].eb(u, i - 1);
		Edge.eb(u, v);
	}
	H[1] = 0;
	DFS(1);
	for(int i = 1; i <= n; i++)
	{
		c[H[i] & 1] += a[i];
	}
	for(int i = 0; i < m; i++)
	{
		pair <int, int> x = Edge[i];
		if(H[x.fi] % 2 == H[x.se] % 2)
		{
			if(H[x.fi] % 2 == 1)
			{
				ans[i] = (c[1] - c[0]) / 2;
				a[x.fi] -= ans[i];
				a[x.se] -= ans[i];
			}
			else
			{
				ans[i] = (c[0] - c[1]) / 2;
				a[x.fi] -= ans[i];
				a[x.se] -= ans[i];
			}
		}
	}
	DFS2(1);
	for(int i = 0; i < m; i++)
	{
		cout << ans[i] * 2 << '\n';
	}
}

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