Submission #125144

#	Time	Username	Problem	Language	Result	Execution time	Memory
125144		thiago4532	Pipes (BOI13_pipes)	C++17	100 / 100	455 ms	24832 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];
bool marca[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);
		}
	}

	vector<int> ciclo;
	for(int i=1;i<=n;i++)
		if(!mark[i]) ciclo.push_back(i);

	if(ciclo.size() == 0) {
		for(int i=1;i<=m;i++)
 			cout << ans[i] << "\n";
 		return 0;
	}
	// cout << "SHITE\n"

	if(ciclo.size() % 2 == 0){
		cout << "0\n";
		return 0;
	}

	vector<int> ordem;
	int k = 0;

	ordem.push_back(ciclo[0]);

	while(k < ordem.size()) {
		int u = ordem[k++];

		if(marca[u]) continue;
		marca[u] = true;

		for(auto v : grafo[u]) {
			if(mark[v] || marca[v]) continue;
			ordem.push_back(v);
			break;
		}
	}

	int sums = 0;
	int val = 1;
	for(auto u : ordem) {
		sums += (s[u] * val);
		val *= -1;
	}
	sums >>= 1;

	ans[mapa[{ordem.back(), ordem.front()}]] = sums;
	int l = sums;

	for(int i = 0; i < (int)ordem.size() - 1;i++) {
		ans[mapa[{ordem[i], ordem[i+1]}]] = s[ordem[i]] - l;
		l = s[ordem[i]] - l;
	}
 	for(int i=1;i<=m;i++)
 		cout << ans[i] << "\n";
	return 0;
}

Compilation message (stderr)

pipes.cpp: In function 'int32_t main()':
pipes.cpp:80:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(k < ordem.size()) {
        ~~^~~~~~~~~~~~~~

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