Submission #84489

#	Time	Username	Problem	Language	Result	Execution time	Memory
84489		Dat160601	Pipes (BOI13_pipes)	C++17	100 / 100	284 ms	17792 KiB

pipes

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int n, m, cnt[100007], vis[500007], u, v, elim = 0, cur = 0, loop = 0;
long long c[100007], ans[500007], sum = 0;
vector < pair <int, int> > edge[100007];

void solve(){
	queue <int> q;
	memset(cnt, 0, sizeof(cnt));
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < (int)edge[i].size(); j++){
			if(vis[edge[i][j].se]) continue;
			cnt[i]++;
		}
		if(cnt[i] == 1) q.push(i);
	}
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(int i = 0; i < (int)edge[u].size(); i++){
			int v = edge[u][i].fi, id = edge[u][i].se;
			//cout << u << " " << v << " " << id << endl;
			if(vis[id]) continue;
			ans[id] = c[u] * 2LL;
			c[u] -= ans[id] / 2LL, c[v] -= ans[id] / 2LL;
			cnt[v]--;
			cnt[u]--;
			vis[id] = true;
			if(cnt[v] == 1) q.push(v);
		}
	}
}

void print(){
	for(int i = 1; i <= n; i++){
		if(c[i] != 0){
			cout << 0;
			exit(0);
		}
	}
	for(int i = 1; i <= m; i++) cout << ans[i] << "\n";
	exit(0);
}

void dfs(int u, int par){
	cur++;
	if(cur & 1) sum += c[u];
	else sum -= c[u];
	for(int i = 0; i < (int)edge[u].size(); i++){
		int v = edge[u][i].fi, id = edge[u][i].se;
		if(v == par || vis[id]) continue;
		if(cur == loop){
			ans[id] = sum;
			c[u] -= sum / 2LL;
			c[v] -= sum / 2LL;
			elim = id;
			vis[elim] = true;
			solve();
			return;
		}
		dfs(v, u);
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> c[i];
	}
	for(int i = 1; i <= m; i++){
		cin >> u >> v;
		edge[u].pb(mp(v, i));
		edge[v].pb(mp(u, i));
	}
	if(m > n) return cout << 0, 0;
	if(m == n - 1){
		solve();
		print();
	}
	solve();
	for(int i = 1; i <= n; i++){
		if(cnt[i] <= 0) continue;
		loop++;
	}
	if(loop % 2 == 0) return cout << 0, 0;
	for(int i = 1; i <= n; i++){
		if(cnt[i] <= 0) continue;
		dfs(i, i);
		break;
	}
	print();
}

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