Submission #298038

#	Time	Username	Problem	Language	Result	Execution time	Memory
298038		miss_robot	Pipes (BOI13_pipes)	C++14	100 / 100	153 ms	19064 KiB

pipes

#include <bits/stdc++.h>

#pragma GCC optimize("O3")

using namespace std;

const int N = 100000, M = 500000;
int n, m, rmv;
int sol[M], active[N], v[N], out[N];
vector<int> g[N], num[N], s;

int solve(int mode, int val, int u, int l, int a, int b){
	if(a == b) return sol[a] = val/2;
	for(int i = 0, w, x; i < (int)g[u].size(); i++){
		w = g[u][i];
		if(w == l || !active[w]) continue;
		if(mode){
			x = solve(0, val+v[u], w, u, a, num[u][i]);
			sol[b] = x - val;
		}
		else{
			x = solve(1, val-v[u], w, u, a, num[u][i]);
			sol[b] = val - x;
		}
		return x;
	}
	return -1;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cin >> n >> m;
	if(m > n){
		cout << "0\n";
		return 0;
	}
	for(int i = 0; i < n; i++) cin >> v[i];
	for(int i = 0, u, w; i < m; i++){
		cin >> u >> w;
		u--, w--;
		g[u].push_back(w), g[w].push_back(u);
		num[u].push_back(i), num[w].push_back(i);
	}
	for(int i = 0; i < n; i++) out[i] = g[i].size(), active[i] = 1;;
	for(int i = 0; i < n; i++) if(out[i] == 1) s.push_back(i);
	while(!s.empty()){
		int u = s.back(), j = -1;
		s.pop_back();
		active[u] = 0, rmv++;
		for(int i = 0; i < (int)g[u].size(); i++) if(active[g[u][i]]) j = i;
		if(j == -1) continue;
		sol[num[u][j]] = v[u];
		v[g[u][j]] -= sol[num[u][j]];
		if(--out[g[u][j]] == 1) s.push_back(g[u][j]);
	}
	if(n-rmv && !((n-rmv)%2)){
		cout << "0\n";
		return 0;
	}
	for(int i = 0, a=-1, b=-1; i < n; i++) if(active[i]){
		for(int j = 0, w; j < (int)g[i].size(); j++){
			w = g[i][j];
			if(!active[w]) continue;
			if(a==-1) a = j;
			else b = j;
		}
		solve(0, v[i], g[i][b], i, num[i][a], num[i][b]);
		break;
	}
	for(int i = 0; i < m; i++) cout << 2*sol[i] << "\n";
}

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