oj.uz

Submission #84488

# Submission time Handle Problem Language Result Execution time Memory
84488 2018-11-15T15:12:38 Z Dat160601 Pipes (BOI13_pipes) C++17
90.9259 / 100
 249 ms 44948 KB 
#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++;
	}
	for(int i = 1; i <= n; i++){
		if(cnt[i] == 0) continue;
		dfs(i, i);
		break;
	}
	print();
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3064 KB Output is correct
2 Correct 4 ms 3200 KB Output is correct
3 Correct 5 ms 3272 KB Output is correct
4 Correct 77 ms 10756 KB Output is correct
5 Correct 4 ms 10756 KB Output is correct
6 Correct 5 ms 10756 KB Output is correct
7 Correct 4 ms 10756 KB Output is correct
8 Correct 4 ms 10756 KB Output is correct
9 Correct 5 ms 10756 KB Output is correct
10 Correct 5 ms 10756 KB Output is correct
11 Correct 5 ms 10756 KB Output is correct
12 Correct 5 ms 10756 KB Output is correct
13 Correct 57 ms 10852 KB Output is correct
14 Correct 70 ms 13256 KB Output is correct
15 Correct 75 ms 14876 KB Output is correct
16 Correct 65 ms 14876 KB Output is correct
17 Correct 83 ms 15228 KB Output is correct
18 Correct 73 ms 15764 KB Output is correct
19 Correct 85 ms 16632 KB Output is correct
20 Correct 4 ms 16632 KB Output is correct
21 Correct 5 ms 16632 KB Output is correct
22 Correct 75 ms 18956 KB Output is correct
23 Correct 58 ms 18956 KB Output is correct
24 Correct 71 ms 19492 KB Output is correct
25 Correct 66 ms 19492 KB Output is correct

Subtask #2
60.9259259259 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19492 KB Output is correct
2 Correct 5 ms 19492 KB Output is correct
3 Incorrect 80 ms 21020 KB Output isn't correct
4 Correct 54 ms 21020 KB Output is correct
5 Correct 60 ms 21020 KB Output is correct
6 Correct 249 ms 32284 KB Output is correct
7 Correct 5 ms 32284 KB Output is correct
8 Correct 4 ms 32284 KB Output is correct
9 Incorrect 4 ms 32284 KB Output isn't correct
10 Correct 4 ms 32284 KB Output is correct
11 Correct 4 ms 32284 KB Output is correct
12 Correct 4 ms 32284 KB Output is correct
13 Correct 4 ms 32284 KB Output is correct
14 Correct 4 ms 32284 KB Output is correct
15 Correct 5 ms 32284 KB Output is correct
16 Correct 5 ms 32284 KB Output is correct
17 Incorrect 5 ms 32284 KB Output isn't correct
18 Correct 4 ms 32284 KB Output is correct
19 Correct 4 ms 32284 KB Output is correct
20 Correct 4 ms 32284 KB Output is correct
21 Correct 5 ms 32284 KB Output is correct
22 Correct 5 ms 32284 KB Output is correct
23 Correct 66 ms 32284 KB Output is correct
24 Correct 89 ms 32284 KB Output is correct
25 Incorrect 78 ms 32284 KB Output isn't correct
26 Correct 55 ms 32284 KB Output is correct
27 Correct 52 ms 32284 KB Output is correct
28 Correct 56 ms 32284 KB Output is correct
29 Correct 179 ms 33460 KB Output is correct
30 Correct 89 ms 33460 KB Output is correct
31 Correct 86 ms 34668 KB Output is correct
32 Correct 77 ms 34668 KB Output is correct
33 Incorrect 79 ms 35792 KB Output isn't correct
34 Correct 52 ms 35792 KB Output is correct
35 Correct 52 ms 35792 KB Output is correct
36 Correct 54 ms 35792 KB Output is correct
37 Correct 248 ms 41692 KB Output is correct
38 Correct 86 ms 41692 KB Output is correct
39 Correct 74 ms 41692 KB Output is correct
40 Correct 85 ms 41692 KB Output is correct
41 Incorrect 97 ms 41692 KB Output isn't correct
42 Correct 65 ms 41692 KB Output is correct
43 Correct 54 ms 41692 KB Output is correct
44 Correct 57 ms 41692 KB Output is correct
45 Correct 174 ms 44948 KB Output is correct
46 Correct 79 ms 44948 KB Output is correct
47 Correct 81 ms 44948 KB Output is correct
48 Correct 86 ms 44948 KB Output is correct
49 Incorrect 72 ms 44948 KB Output isn't correct
50 Correct 54 ms 44948 KB Output is correct
51 Correct 56 ms 44948 KB Output is correct
52 Correct 58 ms 44948 KB Output is correct
53 Correct 188 ms 44948 KB Output is correct
54 Correct 81 ms 44948 KB Output is correct