Submission #1127173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127173		Halym2007	Pipes (BOI13_pipes)	C++17	74.07 / 100	806 ms	83420 KiB

pipes

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
#define dur exit(0)
#define dur1 return(0)
const int N = 2e5 + 5;
ll n, m, val[N], jog[N];
pii par[N];
vector <pii> v[N]; 
vector <int> order, node, cycle;
map <pii, int> mp;
int vis[N], kk[N];

void dfs (int x, int p) {
	for (pii i : v[x]) {
		if (i.ff == p or kk[i.ff] == 1) continue;
		dfs (i.ff, x);
		par[i.ff] = {x, i.ss};
	}
	order.pb (x);
}
int ss = 0;

void cycle_detection (int x, int par) {
	vis[x] = 1;
	node.pb (x);
	for (pii i : v[x]) {
		if (i.ff == par) continue;
		if (vis[i.ff]) {
			int idx = (int)node.sz - 1;
			cycle.pb (i.ff);
			++ss;
			assert (ss <= 1);
			while (1) {
				cycle.pb (node[idx]);
				idx--;
				if (node[idx] == i.ff) break;
				assert (idx >= 0);
			} 
			if ((int)cycle.sz % 2 == 0) {
				cout << "0";
				dur;
			}					
			continue;
		}
		cycle_detection (i.ff, x);
	}
	
	node.pop_back();
}


int main () {
//	freopen ("input1.txt", "r", stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> m;

	for (int i = 1; i <= n; ++i) {
		cin >> val[i];
	}	
	for (int i = 1; i <= m; ++i) {
		int l, r;
		cin >> l >> r;
		mp[{l, r}] = i;
		mp[{r, l}] = i;
		v[l].pb ({r, i});
		v[r].pb ({l, i});
	}
	
	if (n <= m) {
		cout << "0";
		return 0;
	}
	if (n == m) {
		cycle_detection (1, -1);	
		for (int i : cycle) {
			kk[i] = 1;
		}
//			cout << i << " ";
//			return 0;
		for (int i : cycle) {
			dfs (i, -1);
			order.pop_back();
		}	
		assert ((int)cycle.sz % 2 == 1);
		ll gosh = 0;
		for (int i = 0; i < (int)cycle.sz; ++i) {
			if (i % 2 == 0) {
				gosh += val[cycle[i]];
			}
			else {
				gosh -= val[cycle[i]];
			}
		}
		if (gosh % 2 == 0) {
			cout << "0";
			return 0;
		}
		else {
			ll jp = gosh / 2;
			jog[mp[{cycle[0], cycle.back()}]] = jp;
			for (int i = 0; i + 1 < (int)cycle.sz; ++i) {
				jog[mp[{cycle[i], cycle[i + 1]}]] = val[cycle[i]] - jp;
				jp = val[cycle[i]] - jp;
			}
		}
	}
	else {
		dfs (1, -1);
		order.pop_back();
	}
	for (int i : order) {
		val[par[i].ff] -= val[i];
		jog[par[i].ss] = val[i];
	}
	for (int i = 1; i <= m; ++i) {
		cout << jog[i] + jog[i] << "\n";
	}
}

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