Submission #443793

#	Time	Username	Problem	Language	Result	Execution time	Memory
443793		wind_reaper	Pipes (BOI13_pipes)	C++17	74.07 / 100	500 ms	131076 KiB

pipes

#include <bits/stdc++.h>

using namespace std;

#define int int64_t
const int MXN = 100000;

set<array<int, 2>> g[MXN];
int change[MXN];
vector<bool> vis(MXN);

void solve(){
	int N, M;
	cin >> N >> M;

	for(int i = 0; i < N; i++)
		cin >> change[i];

	for(int i = 0; i < M; i++){
		int u, v;
		cin >> u >> v;
		--u, --v;
		g[u].insert({v, i});
		g[v].insert({u, i});
	}

	if(M > N){
		cout << 0 << '\n';
		return;
	}

	queue<array<int, 3>> q;
	for(int i = 0; i < N; i++)
		if(g[i].size() < 2){
			q.push({i, (*g[i].begin())[0], (*g[i].begin())[1]});
			vis[i] = 1;
		}

	int cnt = 0;

	vector<int> ans(M);

	while(!q.empty()){
		auto [u, par, idx] = q.front();
		q.pop();

		++cnt;

		int t = change[u];
		ans[idx] += 2*t;
		change[u] -= t;
		change[par] -= t;

		g[par].erase({u, idx});

		if(g[par].size() == 1 && !vis[par])
			q.push({par, (*g[par].begin())[0], (*g[par].begin())[1]});
	}

	if(cnt < N){
		if(!((N - cnt) & 1)){
			cout << 0 << '\n';
			return;
		}

		int x;
		for(int i = 0; i < N; i++) 
			if(!vis[i]) 
				x = i;

		int u = x;

		vector<int> a, b;

		while(u != x || a.empty()){
			auto [v, idx] = a.empty() || (*g[u].begin())[0] != a.back() ? *g[u].begin() : *g[u].rbegin();
			a.push_back(v);
			b.push_back(idx);
			u = v;
		}

		N = a.size();
		vector<int> suf(N);
		suf[N-1] = change[a[N-1]];
		for(int i = N - 2; i >= 0; --i)
			suf[i] = change[a[i]] - suf[i+1];
		int pre = 0;

		for(int i = 0; i < N; i++){
			pre = change[a[i]] - pre;
			ans[b[i]] = (pre + (i + 1 < N ? suf[i+1] : 0));
		}
	}

	for(int i = 0; i < M; i++)
		cout << ans[i] << '\n';
}

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

	solve();

	return 0; 
}

Compilation message (stderr)

pipes.cpp: In function 'void solve()':
pipes.cpp:75:16: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |   while(u != x || a.empty()){
      |         ~~~~~~~^~~~~~~~~~~~

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