Submission #434389

#	Time	Username	Problem	Language	Result	Execution time	Memory
434389		dutch	Pipes (BOI13_pipes)	C++17	100 / 100	618 ms	74636 KiB

pipes

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
const int MAXN = 1e5;

set<array<int, 2>> h[MAXN];
int c[MAXN], ans[MAXN+1], cnt = 0, suf[MAXN];
bitset<MAXN> vis;

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, m, x, y; cin >> n >> m;
	for(int i=0; i<n; ++i) cin >> c[i];
	for(int i=0; i<m; ++i){
		cin >> x >> y; --x, --y;
		h[x].insert({y, i});
		h[y].insert({x, i});
	}

	if(m > n){
		cout << 0;
		return 0;
	}

	queue<int> q; set<int> s;
	for(int i=0; i<n; ++i) if(h[i].size() < 2) q.push(i), vis[i] = 1;

	while(!q.empty()){
		int u = q.front(); q.pop();
		++cnt;
		array<int, 2> e = *h[u].begin();
		ans[e[1]] += c[u];
		c[e[0]] -= c[u];
		h[e[0]].erase({u, e[1]});
		if(h[e[0]].size() < 2 && !vis[e[0]]) q.push(e[0]), vis[e[0]] = 1;
	}

	if(cnt < n){
		if(!((n-cnt) & 1)){
			cout << 0;
			return 0;
		}
		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 = a.empty() || (*h[u].begin())[0] != a.back() ? *h[u].begin() : *h[u].rbegin();
			a.push_back(u);
			b.push_back(v[1]);
			u = v[0];
		}
		n = a.size();
		int pre = 0;
		suf[n-1] = c[a[n-1]];
		for(int i=n-2; i>=0; --i) suf[i] = c[a[i]] - suf[i+1];
		for(int i=0; i<n; ++i){
			pre = c[a[i]] - pre;
			ans[b[i]] = (pre + (i+1 < n ? suf[i+1] : 0LL))/2LL;
		}
	}

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

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