oj.uz

Submission #319028

# Submission time Handle Problem Language Result Execution time Memory
319028 2020-11-03T18:34:06 Z rqi Pipes (BOI13_pipes) C++14
87.037 / 100
 374 ms 36072 KB 
#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){
			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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Correct 3 ms 2796 KB Output is correct
4 Correct 143 ms 12524 KB Output is correct
5 Correct 2 ms 2668 KB Output is correct
6 Correct 2 ms 2668 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Correct 2 ms 2668 KB Output is correct
9 Correct 3 ms 2796 KB Output is correct
10 Correct 4 ms 2796 KB Output is correct
11 Correct 3 ms 2796 KB Output is correct
12 Correct 3 ms 2796 KB Output is correct
13 Correct 106 ms 10212 KB Output is correct
14 Correct 126 ms 11620 KB Output is correct
15 Correct 150 ms 12172 KB Output is correct
16 Correct 131 ms 10724 KB Output is correct
17 Correct 137 ms 12136 KB Output is correct
18 Correct 137 ms 12128 KB Output is correct
19 Correct 146 ms 16228 KB Output is correct
20 Correct 2 ms 2668 KB Output is correct
21 Correct 3 ms 2796 KB Output is correct
22 Correct 139 ms 12132 KB Output is correct
23 Correct 111 ms 10212 KB Output is correct
24 Correct 136 ms 12132 KB Output is correct
25 Correct 118 ms 10600 KB Output is correct

Subtask #2
57.037037037 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Runtime error 7 ms 5612 KB Execution killed with signal 6 (could be triggered by violating memory limits)
3 Correct 128 ms 13776 KB Output is correct
4 Correct 126 ms 14592 KB Output is correct
5 Correct 163 ms 11616 KB Output is correct
6 Correct 369 ms 18532 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Correct 2 ms 2668 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 2 ms 2668 KB Output is correct
12 Correct 2 ms 2668 KB Output is correct
13 Correct 2 ms 2668 KB Output is correct
14 Correct 2 ms 2668 KB Output is correct
15 Runtime error 7 ms 5612 KB Execution killed with signal 6 (could be triggered by violating memory limits)
16 Runtime error 7 ms 5484 KB Execution killed with signal 6 (could be triggered by violating memory limits)
17 Correct 3 ms 2796 KB Output is correct
18 Correct 3 ms 2796 KB Output is correct
19 Correct 3 ms 2796 KB Output is correct
20 Correct 3 ms 2796 KB Output is correct
21 Correct 4 ms 2924 KB Output is correct
22 Runtime error 7 ms 5484 KB Execution killed with signal 6 (could be triggered by violating memory limits)
23 Correct 122 ms 12644 KB Output is correct
24 Runtime error 158 ms 28900 KB Execution killed with signal 6 (could be triggered by violating memory limits)
25 Correct 123 ms 13284 KB Output is correct
26 Correct 132 ms 16484 KB Output is correct
27 Correct 138 ms 17016 KB Output is correct
28 Correct 142 ms 11544 KB Output is correct
29 Correct 310 ms 16740 KB Output is correct
30 Runtime error 177 ms 35684 KB Execution killed with signal 6 (could be triggered by violating memory limits)
31 Correct 164 ms 18080 KB Output is correct
32 Correct 145 ms 12772 KB Output is correct
33 Correct 126 ms 14692 KB Output is correct
34 Correct 135 ms 15972 KB Output is correct
35 Correct 125 ms 14180 KB Output is correct
36 Correct 123 ms 11236 KB Output is correct
37 Correct 374 ms 18532 KB Output is correct
38 Runtime error 157 ms 27620 KB Execution killed with signal 6 (could be triggered by violating memory limits)
39 Correct 147 ms 12520 KB Output is correct
40 Runtime error 162 ms 27492 KB Execution killed with signal 6 (could be triggered by violating memory limits)
41 Correct 130 ms 18148 KB Output is correct
42 Correct 128 ms 18276 KB Output is correct
43 Correct 127 ms 15588 KB Output is correct
44 Correct 120 ms 11108 KB Output is correct
45 Correct 291 ms 13668 KB Output is correct
46 Correct 166 ms 16996 KB Output is correct
47 Runtime error 163 ms 28260 KB Execution killed with signal 6 (could be triggered by violating memory limits)
48 Runtime error 163 ms 36072 KB Execution killed with signal 6 (could be triggered by violating memory limits)
49 Correct 121 ms 12004 KB Output is correct
50 Correct 130 ms 15464 KB Output is correct
51 Correct 123 ms 13156 KB Output is correct
52 Correct 121 ms 12552 KB Output is correct
53 Correct 318 ms 15588 KB Output is correct
54 Correct 156 ms 16228 KB Output is correct