Submission #85888

#	Time	Username	Problem	Language	Result	Execution time	Memory
85888		fasterthanyou	Pipes (BOI13_pipes)	C++14	54.59 / 100	1067 ms	83972 KiB

pipes

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

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

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

		dfs(v, u);
		child[u] += child[v] + 1;
		p[v] = u;
	}
}

void caseTree()
{
	p[1] = -1;
	dfs(1, -1);

	for (int i = 2; i <= n; ++i)
		if (child[i] == 0) q.push(i);	
	for (int i = 1; i <= n; ++i)
		tmp[i] = child[i];

	while (!q.empty())
	{
		int u = q.front(); q.pop();
		d[p[u]] -= d[u];
		child[p[u]] -= (tmp[u] + 1);

		if (p[u] != -1) res[mp[{u, p[u]}]] = d[u];
		if (child[p[u]] < 1 && p[u] != -1) q.push(p[u]);
	}
	for (int id = 1; id <= m; ++id)
		cout << res[id] << '\n';
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	//freopen("pipes.inp", "r", stdin);
	//freopen("pipes.out", "w", stdout);

	cin >> n >> m;
	d.resize(n + 1);
	child.resize(n + 1, 0);
	tmp.resize(n + 1);
	p.resize(n + 1);
	res.resize(m + 1);
	vst.resize(n + 1, 0);

	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 + 1,
		mp[{v, u}] = i + 1;

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

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