oj.uz

답안 #319027

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
319027 2020-11-03T18:31:56 Z rqi Pipes (BOI13_pipes) C++14
77.963 / 100
 375 ms 36452 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){
			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.0 / 30.0

# 결과 실행 시간 메모리 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 139 ms 11108 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 3 ms 2668 KB Output is correct
9 Correct 3 ms 2796 KB Output is correct
10 Correct 3 ms 2796 KB Output is correct
11 Correct 4 ms 2796 KB Output is correct
12 Correct 3 ms 2796 KB Output is correct
13 Correct 124 ms 9956 KB Output is correct
14 Correct 129 ms 11236 KB Output is correct
15 Correct 144 ms 11748 KB Output is correct
16 Correct 124 ms 10596 KB Output is correct
17 Correct 145 ms 11620 KB Output is correct
18 Correct 143 ms 11620 KB Output is correct
19 Correct 151 ms 15972 KB Output is correct
20 Correct 2 ms 2668 KB Output is correct
21 Correct 3 ms 2796 KB Output is correct
22 Correct 142 ms 11616 KB Output is correct
23 Correct 110 ms 9956 KB Output is correct
24 Correct 138 ms 11620 KB Output is correct
25 Correct 114 ms 10340 KB Output is correct

Subtask #2
47.962962963 / 70.0

# 결과 실행 시간 메모리 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 Runtime error 143 ms 26212 KB Execution killed with signal 6 (could be triggered by violating memory limits)
4 Correct 130 ms 14308 KB Output is correct
5 Correct 127 ms 11108 KB Output is correct
6 Correct 371 ms 17728 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Correct 3 ms 2668 KB Output is correct
9 Runtime error 7 ms 5356 KB Execution killed with signal 6 (could be triggered by violating memory limits)
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 2664 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 Runtime error 9 ms 5484 KB Execution killed with signal 6 (could be triggered by violating memory limits)
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 2796 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 129 ms 13412 KB Output is correct
24 Runtime error 163 ms 29240 KB Execution killed with signal 6 (could be triggered by violating memory limits)
25 Runtime error 140 ms 26468 KB Execution killed with signal 6 (could be triggered by violating memory limits)
26 Correct 136 ms 16996 KB Output is correct
27 Correct 129 ms 17580 KB Output is correct
28 Correct 128 ms 11620 KB Output is correct
29 Correct 324 ms 17252 KB Output is correct
30 Runtime error 168 ms 36196 KB Execution killed with signal 6 (could be triggered by violating memory limits)
31 Correct 178 ms 18404 KB Output is correct
32 Correct 154 ms 13284 KB Output is correct
33 Runtime error 148 ms 29284 KB Execution killed with signal 6 (could be triggered by violating memory limits)
34 Correct 162 ms 16356 KB Output is correct
35 Correct 130 ms 14524 KB Output is correct
36 Correct 123 ms 11616 KB Output is correct
37 Correct 375 ms 18532 KB Output is correct
38 Runtime error 183 ms 28004 KB Execution killed with signal 6 (could be triggered by violating memory limits)
39 Correct 154 ms 13028 KB Output is correct
40 Runtime error 157 ms 27748 KB Execution killed with signal 6 (could be triggered by violating memory limits)
41 Runtime error 158 ms 36116 KB Execution killed with signal 6 (could be triggered by violating memory limits)
42 Correct 140 ms 18660 KB Output is correct
43 Correct 128 ms 15968 KB Output is correct
44 Correct 126 ms 11556 KB Output is correct
45 Correct 292 ms 13924 KB Output is correct
46 Correct 158 ms 17380 KB Output is correct
47 Runtime error 155 ms 28388 KB Execution killed with signal 6 (could be triggered by violating memory limits)
48 Runtime error 174 ms 36452 KB Execution killed with signal 6 (could be triggered by violating memory limits)
49 Runtime error 137 ms 23652 KB Execution killed with signal 6 (could be triggered by violating memory limits)
50 Correct 133 ms 15716 KB Output is correct
51 Correct 131 ms 13412 KB Output is correct
52 Correct 127 ms 12772 KB Output is correct
53 Correct 312 ms 15460 KB Output is correct
54 Correct 175 ms 16616 KB Output is correct