Submission #1127264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127264		Agageldi	Pipes (BOI13_pipes)	C++20	88.33 / 100	622 ms	93604 KiB

pipes

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define N 600005
#define ff first
#define ss second
#define pb push_back
#define sz(s) (int)s.size()

ll n, m, par[N], a[N], vis[N], c[N], sum, tr;
vector <ll> v[N], e;
vector <pair <ll,ll>> ans;
map <pair<ll,ll>,ll> vip;

void solve(int x) {
	vis[x] = 1;
	for(auto i : v[x]) {
		if(!vis[i]) {
			par[i] = x;
			solve(i);
			if(!c[i]) {
				ans.pb({vip[{i,x}],a[i]});
				// cout << x << " " << i<< " " << a[x] << " " << a[i]<< '\n';
				a[x] -= a[i];
			}
			continue;
		}
		if(i != par[x] && c[i] == 0) {
			int p = x;
			e.pb(i);
			while(p != i) {
				e.pb(p);
				c[p] = 1;
				p = par[p];
			}
			e.pb(i);
			// reverse(e.begin(),e.end());
			c[i] = 1;
			if(sz(e) % 2) {
				cout << "0\n";
				exit(0);
			}
		}
	}
}

int main () {
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n; i++) {
		cin >> a[i];
		par[i] = i;
	}
	for(int i = 1;i <= m; i++) {
		ll x, y;
		cin >> x >> y;
		v[x].pb(y);
		v[y].pb(x);
		vip[{x,y}] = i;
		vip[{y,x}] = i;
	}
	if(n < m) {
		cout << '0' << '\n';
		return 0;
	}
	solve(1);
	bool t = 0;
	for(int i = 0; i < sz(e) - 1; i++) {
		if(!t)sum += a[e[i]];
		else sum -= a[e[i]];
		t = 1 - t;
	}
	reverse(e.begin(),e.end());
	sum /= 2;
	for(int i = 0;i<sz(e)- 1;i++) {
		ans.pb({vip[{e[i],e[i+1]}],sum});
		sum = a[e[i+1]] - sum;
	}
	sort(ans.begin(),ans.end());
	for(auto i:ans) {
		cout << i.ss * 2 << '\n';
	}
}

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