Submission #85881

#	Time	Username	Problem	Language	Result	Execution time	Memory
85881		fasterthanyou	Pipes (BOI13_pipes)	C++11	29.81 / 100	1084 ms	132096 KiB

pipes

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
using namespace std;

int n, m, child[100015], p[100015];
bool vst[100015];
long long d[100015], res[500015];
vector<int> g[100015];
map<pair<int, int>, int> mp;

void dfs (int u)
{
	vst[u] = 1;
	child[u] = 0;
	for (int i = 0; i < (int)g[u].size(); ++i)
	{
		int v = g[u][i];
		if (!vst[v])
		{
			dfs(v);
			child[u] += 1 + child[v];
			p[v] = u;
		}
	}
}

void caseTree()
{
	dfs(1);
	while (child[1] > 0)
	{
		for (int u = 1; u <= n; ++u)
			if (child[u] < 1)
			{
				d[p[u]] -= d[u];
				--child[p[u]];
				res[mp[{u, p[u]}]] = d[u];
			}
	}

	if (d[1] != 0) cout << 0;
	else
	{
		for (int id = 0; id < m; ++id)
			cout << res[id] << '\n';
	}
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
		cin >> d[i],
		d[i] *= 2;
	for (int i = 0, u, v; i < m; ++i)
		cin >> u >> v,
		g[u].push_back(v),
		g[v].push_back(u),
		mp[{u, v}] = i,
		mp[{v, u}] = i;

	if (m == n - 1) 
		caseTree();
	else if (n < m)
		cout << 0;
}

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