답안 #84271 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
84271	2018-11-14T04:25:08 Z	Dat160601	Pipes (BOI13_pipes)	C++17	76.6667 / 100	249 ms	17644 KB

pipes

#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(edge[i][j].se == elim) continue;
			cnt[i]++;
		}
		if(cnt[i] == 1) q.push(i);
	}
	vis[elim] = true;
	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;
			solve();
			print();
			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);
	}
}

Subtask #1
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	3064 KB	Output is correct
2	Correct	5 ms	3196 KB	Output is correct
3	Correct	7 ms	3264 KB	Output is correct
4	Correct	99 ms	9556 KB	Output is correct
5	Correct	4 ms	9556 KB	Output is correct
6	Correct	4 ms	9556 KB	Output is correct
7	Correct	4 ms	9556 KB	Output is correct
8	Correct	4 ms	9556 KB	Output is correct
9	Correct	5 ms	9556 KB	Output is correct
10	Correct	5 ms	9556 KB	Output is correct
11	Correct	5 ms	9556 KB	Output is correct
12	Correct	5 ms	9556 KB	Output is correct
13	Correct	57 ms	9556 KB	Output is correct
14	Correct	68 ms	9556 KB	Output is correct
15	Correct	70 ms	9608 KB	Output is correct
16	Correct	70 ms	9608 KB	Output is correct
17	Correct	81 ms	9664 KB	Output is correct
18	Correct	70 ms	9672 KB	Output is correct
19	Correct	68 ms	9672 KB	Output is correct
20	Correct	4 ms	9672 KB	Output is correct
21	Correct	5 ms	9672 KB	Output is correct
22	Correct	73 ms	9676 KB	Output is correct
23	Correct	69 ms	9676 KB	Output is correct
24	Correct	77 ms	9676 KB	Output is correct
25	Correct	62 ms	9676 KB	Output is correct

Subtask #2
46.6666666667 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	4 ms	9676 KB	Output isn't correct
2	Incorrect	5 ms	9676 KB	Output isn't correct
3	Correct	68 ms	10744 KB	Output is correct
4	Correct	53 ms	10744 KB	Output is correct
5	Correct	52 ms	10744 KB	Output is correct
6	Correct	238 ms	17644 KB	Output is correct
7	Incorrect	5 ms	17644 KB	Output isn't correct
8	Incorrect	4 ms	17644 KB	Output isn't correct
9	Correct	6 ms	17644 KB	Output is correct
10	Correct	4 ms	17644 KB	Output is correct
11	Correct	4 ms	17644 KB	Output is correct
12	Correct	4 ms	17644 KB	Output is correct
13	Correct	4 ms	17644 KB	Output is correct
14	Incorrect	4 ms	17644 KB	Output isn't correct
15	Incorrect	6 ms	17644 KB	Output isn't correct
16	Incorrect	6 ms	17644 KB	Output isn't correct
17	Correct	5 ms	17644 KB	Output is correct
18	Correct	5 ms	17644 KB	Output is correct
19	Correct	6 ms	17644 KB	Output is correct
20	Correct	5 ms	17644 KB	Output is correct
21	Correct	5 ms	17644 KB	Output is correct
22	Incorrect	5 ms	17644 KB	Output isn't correct
23	Incorrect	59 ms	17644 KB	Output isn't correct
24	Correct	86 ms	17644 KB	Output is correct
25	Correct	67 ms	17644 KB	Output is correct
26	Correct	100 ms	17644 KB	Output is correct
27	Correct	64 ms	17644 KB	Output is correct
28	Correct	57 ms	17644 KB	Output is correct
29	Correct	181 ms	17644 KB	Output is correct
30	Incorrect	67 ms	17644 KB	Output isn't correct
31	Incorrect	65 ms	17644 KB	Output isn't correct
32	Incorrect	68 ms	17644 KB	Output isn't correct
33	Incorrect	79 ms	17644 KB	Output isn't correct
34	Correct	51 ms	17644 KB	Output is correct
35	Correct	53 ms	17644 KB	Output is correct
36	Correct	53 ms	17644 KB	Output is correct
37	Correct	249 ms	17644 KB	Output is correct
38	Incorrect	66 ms	17644 KB	Output isn't correct
39	Incorrect	77 ms	17644 KB	Output isn't correct
40	Correct	88 ms	17644 KB	Output is correct
41	Correct	67 ms	17644 KB	Output is correct
42	Correct	105 ms	17644 KB	Output is correct
43	Correct	54 ms	17644 KB	Output is correct
44	Correct	55 ms	17644 KB	Output is correct
45	Correct	187 ms	17644 KB	Output is correct
46	Incorrect	66 ms	17644 KB	Output isn't correct
47	Correct	82 ms	17644 KB	Output is correct
48	Incorrect	64 ms	17644 KB	Output isn't correct
49	Correct	66 ms	17644 KB	Output is correct
50	Correct	59 ms	17644 KB	Output is correct
51	Correct	54 ms	17644 KB	Output is correct
52	Correct	58 ms	17644 KB	Output is correct
53	Correct	187 ms	17644 KB	Output is correct
54	Incorrect	67 ms	17644 KB	Output isn't correct

답안 #84271

Compilation message

Subtask #1 30.0 / 30.0

Subtask #2 46.6666666667 / 70.0

Subtask #1
30.0 / 30.0

Subtask #2
46.6666666667 / 70.0