Submission #85889

#	Time	Username	Problem	Language	Result	Execution time	Memory
85889		fasterthanyou	Pipes (BOI13_pipes)	C++14	74.07 / 100	292 ms	17696 KiB

pipes

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
using namespace std;
 
int n, m, child[100015], tmp[100015];
long long d[100015], res[500015];
vector<pair<int, int> > g[100015];
pair<int, int> p[100015];
queue<int> q;
 
void dfs (int u, int pv)
{
	child[u] = 0;
	for (int i = 0; i < (int)g[u].size(); ++i)
	{
		int v = g[u][i].first;
		if (v == pv) continue;
 
		dfs(v, u);
		child[u] += child[v] + 1;
		p[v] = {u, g[u][i].second};
	}
}
 
void caseTree()
{
	p[1] = {-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].first] -= d[u];
		child[p[u].first] -= (tmp[u] + 1);
 
		if (p[u].first != -1) res[p[u].second] = d[u];
		if (child[p[u].first] < 1 && p[u].first != -1) q.push(p[u].first);
	}
	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;
	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, i + 1}),
		g[v].push_back({u, i + 1});
 
	if (m == n - 1) 
		caseTree();
	else cout << 0;
}

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