Submission #1127811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127811		Agageldi	Pipes (BOI13_pipes)	C++20	100 / 100	695 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], flag,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]) continue;
		solve(i);
		if(!c[i]) {
			ans.pb({vip[{i,x}],a[i]});
			a[x] -= a[i];
		}
	}
}
void find_cycle(int x) {
	vis[x] = 1;
	for(auto i:v[x]) {
		if(tr) continue;
		if(vis[i] == 1 && par[x] != i) {
			e.pb(i);
			while(x != i) {
				e.pb(x);
				x = par[x];
			}
			e.pb(i);
			reverse(e.begin(),e.end());
			if((sz(e) - 1) % 2 == 0) {
				cout << "0\n";
				exit(0);
			}
			tr = 1;
			return;
		}
		if(vis[i]) continue;
		par[i] = x;
		find_cycle(i);
	}
}

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;
	}
	find_cycle(1);
	for(auto i : e) {
		c[i] = 1;
	}
	for(int i = 1; i <= n; i++) {
		vis[i] = 0;
	}
	if(!sz(e)) e.pb(1);
	solve(e[0]);
	bool t = 0;
	for(int i = 0;i < sz(e) - 1;i++) {
		if(t % 2 == 0) sum += a[e[i]];
		else sum -= a[e[i]];
		t = 1 - t;
	}
	sum /= 2;
	reverse(e.begin(),e.end());
	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: 70 / 70