답안 #84272 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
84272	2018-11-14T05:09:51 Z	Dat160601	Pipes (BOI13_pipes)	C++17	76.6667 / 100	312 ms	17708 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();
			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

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	3064 KB	Output is correct
2	Correct	5 ms	3196 KB	Output is correct
3	Correct	5 ms	3244 KB	Output is correct
4	Correct	90 ms	9464 KB	Output is correct
5	Correct	4 ms	9464 KB	Output is correct
6	Correct	4 ms	9464 KB	Output is correct
7	Correct	5 ms	9464 KB	Output is correct
8	Correct	4 ms	9464 KB	Output is correct
9	Correct	5 ms	9464 KB	Output is correct
10	Correct	5 ms	9464 KB	Output is correct
11	Correct	5 ms	9464 KB	Output is correct
12	Correct	5 ms	9464 KB	Output is correct
13	Correct	59 ms	9464 KB	Output is correct
14	Correct	69 ms	9464 KB	Output is correct
15	Correct	78 ms	9656 KB	Output is correct
16	Correct	63 ms	9656 KB	Output is correct
17	Correct	71 ms	9688 KB	Output is correct
18	Correct	75 ms	9688 KB	Output is correct
19	Correct	69 ms	9688 KB	Output is correct
20	Correct	4 ms	9688 KB	Output is correct
21	Correct	4 ms	9688 KB	Output is correct
22	Correct	121 ms	9696 KB	Output is correct
23	Correct	66 ms	9696 KB	Output is correct
24	Correct	72 ms	9708 KB	Output is correct
25	Correct	68 ms	9708 KB	Output is correct

Subtask #2
46.6666666667 / 70.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	5 ms	9708 KB	Output isn't correct
2	Incorrect	5 ms	9708 KB	Output isn't correct
3	Correct	62 ms	10732 KB	Output is correct
4	Correct	59 ms	10732 KB	Output is correct
5	Correct	54 ms	10732 KB	Output is correct
6	Correct	241 ms	17708 KB	Output is correct
7	Incorrect	4 ms	17708 KB	Output isn't correct
8	Incorrect	4 ms	17708 KB	Output isn't correct
9	Correct	4 ms	17708 KB	Output is correct
10	Correct	5 ms	17708 KB	Output is correct
11	Correct	4 ms	17708 KB	Output is correct
12	Correct	4 ms	17708 KB	Output is correct
13	Correct	4 ms	17708 KB	Output is correct
14	Incorrect	4 ms	17708 KB	Output isn't correct
15	Incorrect	5 ms	17708 KB	Output isn't correct
16	Incorrect	5 ms	17708 KB	Output isn't correct
17	Correct	5 ms	17708 KB	Output is correct
18	Correct	5 ms	17708 KB	Output is correct
19	Correct	5 ms	17708 KB	Output is correct
20	Correct	4 ms	17708 KB	Output is correct
21	Correct	5 ms	17708 KB	Output is correct
22	Incorrect	5 ms	17708 KB	Output isn't correct
23	Incorrect	54 ms	17708 KB	Output isn't correct
24	Correct	98 ms	17708 KB	Output is correct
25	Correct	65 ms	17708 KB	Output is correct
26	Correct	75 ms	17708 KB	Output is correct
27	Correct	57 ms	17708 KB	Output is correct
28	Correct	62 ms	17708 KB	Output is correct
29	Correct	186 ms	17708 KB	Output is correct
30	Incorrect	67 ms	17708 KB	Output isn't correct
31	Incorrect	72 ms	17708 KB	Output isn't correct
32	Incorrect	67 ms	17708 KB	Output isn't correct
33	Incorrect	81 ms	17708 KB	Output isn't correct
34	Correct	60 ms	17708 KB	Output is correct
35	Correct	70 ms	17708 KB	Output is correct
36	Correct	68 ms	17708 KB	Output is correct
37	Correct	312 ms	17708 KB	Output is correct
38	Incorrect	130 ms	17708 KB	Output isn't correct
39	Incorrect	68 ms	17708 KB	Output isn't correct
40	Correct	80 ms	17708 KB	Output is correct
41	Correct	90 ms	17708 KB	Output is correct
42	Correct	58 ms	17708 KB	Output is correct
43	Correct	53 ms	17708 KB	Output is correct
44	Correct	53 ms	17708 KB	Output is correct
45	Correct	178 ms	17708 KB	Output is correct
46	Incorrect	85 ms	17708 KB	Output isn't correct
47	Correct	79 ms	17708 KB	Output is correct
48	Incorrect	67 ms	17708 KB	Output isn't correct
49	Correct	75 ms	17708 KB	Output is correct
50	Correct	62 ms	17708 KB	Output is correct
51	Correct	64 ms	17708 KB	Output is correct
52	Correct	55 ms	17708 KB	Output is correct
53	Correct	215 ms	17708 KB	Output is correct
54	Incorrect	67 ms	17708 KB	Output isn't correct

답안 #84272

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