Submission #319027

#	Time	Username	Problem	Language	Result	Execution time	Memory
319027		rqi	Pipes (BOI13_pipes)	C++14	77.96 / 100	375 ms	36452 KiB

pipes

#include <bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<pi> vpi;

#define mp make_pair
#define f first
#define s second
#define pb push_back

struct DSU{
	vi e;
	void init(int n){
		e = vi(n, -1);
	}
	int get(int a){
		if(e[a] < 0) return a;
		e[a] = get(e[a]);
		return e[a];
	}
	bool unite(int a, int b){
		a = get(a);
		b = get(b);
		if(a == b) return 0;
		if(-e[a] < -e[b]) swap(a, b);
		e[b] = a;
		return 1;
	}
};

const int mx = 500005;
const int mx1 = 100005;
int N, M;
ll c[mx1];
ll origc[mx1];
int u[mx];
int v[mx];
ll x[mx];

bool inTree[mx1];
vpi adj[mx1];

int depth[mx1];

void genTree(int node, int prv = -1, int d = 0){
	depth[node] = d;
	for(auto u: adj[node]){
		if(u.f == prv) continue;
		genTree(u.f, node, d+1);
		ll val = c[u.f];
		x[u.s]+=val;
		c[u.f]-=val;
		c[node]-=val;
	}
}

int main(){
	cin >> N >> M;
	DSU dsu;
	dsu.init(N+5);
	for(int i = 1; i <= N; i++){
		cin >> c[i];
		origc[i] = c[i];
	}
	for(int i = 1; i <= M; i++){
		cin >> u[i] >> v[i];
		if(dsu.unite(u[i], v[i])){
			inTree[i] = 1;
			adj[u[i]].pb(mp(v[i], i));
			adj[v[i]].pb(mp(u[i], i));
		}
	}

	genTree(1);

	if(M == N-1){ //Good
		if(c[1] != 0){
			assert(0==1);
			cout << 0 << "\n";
			return 0;
		}
		for(int i = 1; i <= M; i++){
			cout << 2*x[i] << "\n";
		}
		return 0;
	}

	if(M >= N+1){
		cout << 0 << "\n";
		return 0;
	}

	for(int i = 1; i <= M; i++){
		if(inTree[i]) continue;
		if(depth[u[i]] % 2 != depth[v[i]] % 2){
			assert(0==1);
			cout << 0 << "\n";
			return 0;
		}
		for(int j = 1; j <= M; j++){
			x[j] = 0;
		}
		x[i] = c[1]/2;
		for(int j = 1; j <= N; j++){
			c[j] = origc[j];
		}
		c[u[i]]-=x[i];
		c[v[i]]-=x[i];
		genTree(1);
		assert(c[1] == 0);
	}


	for(int i = 1; i <= M; i++){
		cout << 2*x[i] << "\n";
	}

}

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