Submission #1127237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127237		Agageldi	Pipes (BOI13_pipes)	C++20	74.07 / 100	770 ms	92808 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], viss[N], c[N], sum;
vector <ll> v[N], e;
vector <pair <ll,ll>> ans;
map <pair<ll,ll>,ll> vip;

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

int main () {
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n; i++) {
		cin >> a[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);
	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: 44.0741 / 70