Submission #125137

#	Time	Username	Problem	Language	Result	Execution time	Memory
125137		thiago4532	Pipes (BOI13_pipes)	C++17	74.07 / 100	408 ms	23740 KiB

pipes

#include <bits/stdc++.h>
#define int int64_t

using namespace std;
const int maxn = 1e5 + 10;
bool mark[maxn];
int ans[5*maxn], s[maxn], grau[maxn];
map<pair<int, int>, int> mapa;
int n;
vector<int> grafo[maxn];

int32_t main() {
	int m;

	cin >> n >> m;
	if(m >= n) {
		cout << "0\n";
		return 0;
	}
	int total = 0;
	for(int i=1;i<=n;i++)
		cin >> s[i], s[i] *= 2, total += s[i];

	for(int i=1;i<=m;i++) {
		int a, b;
		cin >> a >> b;
		grafo[a].push_back(b);
		grafo[b].push_back(a);
		mapa[{a, b}] = i;
		mapa[{b, a}] = i;

		grau[a]++;
		grau[b]++;
	}
	
	queue<int> fila;
	for(int i=1;i<=n;i++) {
		if(grau[i] == 1)
			fila.push(i);
	}

	while(!fila.empty()) {
		int u = fila.front();
		fila.pop();
		
		if(mark[u]) continue;
		mark[u] = true;

		// cout << u << ": " << s[u] << "\n";
		for(auto v : grafo[u]) {
			if(mark[v]) continue;
			grau[v]--;

			ans[mapa[{u, v}]] = s[u], s[v] -= s[u];
			if(grau[v] == 1) fila.push(v);
		}
	}
 	for(int i=1;i<=m;i++)
 		cout << ans[i] << "\n";
	return 0;
}

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