답안 #84270 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
84270	2018-11-14T04:24:15 Z	Dat160601	Pipes (BOI13_pipes)	C++17	65 / 100	1000 ms	17672 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);
	}
}

Subtask #1
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	3064 KB	Output is correct
2	Correct	4 ms	3064 KB	Output is correct
3	Correct	5 ms	3208 KB	Output is correct
4	Correct	73 ms	9348 KB	Output is correct
5	Correct	4 ms	9348 KB	Output is correct
6	Correct	4 ms	9348 KB	Output is correct
7	Correct	4 ms	9348 KB	Output is correct
8	Correct	4 ms	9348 KB	Output is correct
9	Correct	5 ms	9348 KB	Output is correct
10	Correct	5 ms	9348 KB	Output is correct
11	Correct	5 ms	9348 KB	Output is correct
12	Correct	5 ms	9348 KB	Output is correct
13	Correct	58 ms	9348 KB	Output is correct
14	Correct	70 ms	9348 KB	Output is correct
15	Correct	85 ms	9676 KB	Output is correct
16	Correct	65 ms	9676 KB	Output is correct
17	Correct	76 ms	9676 KB	Output is correct
18	Correct	72 ms	9676 KB	Output is correct
19	Correct	72 ms	9676 KB	Output is correct
20	Correct	4 ms	9676 KB	Output is correct
21	Correct	5 ms	9676 KB	Output is correct
22	Correct	73 ms	9676 KB	Output is correct
23	Correct	59 ms	9676 KB	Output is correct
24	Correct	71 ms	9676 KB	Output is correct
25	Correct	59 ms	9676 KB	Output is correct

Subtask #2
35.0 / 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	Execution timed out	1060 ms	10912 KB	Time limit exceeded
4	Correct	56 ms	10912 KB	Output is correct
5	Correct	57 ms	10912 KB	Output is correct
6	Correct	238 ms	17672 KB	Output is correct
7	Incorrect	5 ms	17672 KB	Output isn't correct
8	Incorrect	4 ms	17672 KB	Output isn't correct
9	Incorrect	4 ms	17672 KB	Output isn't correct
10	Correct	4 ms	17672 KB	Output is correct
11	Correct	4 ms	17672 KB	Output is correct
12	Correct	4 ms	17672 KB	Output is correct
13	Correct	4 ms	17672 KB	Output is correct
14	Incorrect	4 ms	17672 KB	Output isn't correct
15	Incorrect	5 ms	17672 KB	Output isn't correct
16	Incorrect	7 ms	17672 KB	Output isn't correct
17	Incorrect	10 ms	17672 KB	Output isn't correct
18	Correct	4 ms	17672 KB	Output is correct
19	Correct	4 ms	17672 KB	Output is correct
20	Correct	4 ms	17672 KB	Output is correct
21	Correct	5 ms	17672 KB	Output is correct
22	Incorrect	6 ms	17672 KB	Output isn't correct
23	Execution timed out	1069 ms	17672 KB	Time limit exceeded
24	Incorrect	78 ms	17672 KB	Output isn't correct
25	Execution timed out	1070 ms	17672 KB	Time limit exceeded
26	Correct	52 ms	17672 KB	Output is correct
27	Correct	55 ms	17672 KB	Output is correct
28	Correct	60 ms	17672 KB	Output is correct
29	Correct	197 ms	17672 KB	Output is correct
30	Execution timed out	1076 ms	17672 KB	Time limit exceeded
31	Execution timed out	1066 ms	17672 KB	Time limit exceeded
32	Execution timed out	1061 ms	17672 KB	Time limit exceeded
33	Incorrect	77 ms	17672 KB	Output isn't correct
34	Correct	56 ms	17672 KB	Output is correct
35	Correct	52 ms	17672 KB	Output is correct
36	Correct	56 ms	17672 KB	Output is correct
37	Correct	245 ms	17672 KB	Output is correct
38	Execution timed out	1070 ms	17672 KB	Time limit exceeded
39	Execution timed out	1051 ms	17672 KB	Time limit exceeded
40	Incorrect	102 ms	17672 KB	Output isn't correct
41	Execution timed out	1079 ms	17672 KB	Time limit exceeded
42	Correct	55 ms	17672 KB	Output is correct
43	Correct	67 ms	17672 KB	Output is correct
44	Correct	54 ms	17672 KB	Output is correct
45	Correct	180 ms	17672 KB	Output is correct
46	Execution timed out	1082 ms	17672 KB	Time limit exceeded
47	Incorrect	70 ms	17672 KB	Output isn't correct
48	Execution timed out	1070 ms	17672 KB	Time limit exceeded
49	Execution timed out	1071 ms	17672 KB	Time limit exceeded
50	Correct	53 ms	17672 KB	Output is correct
51	Correct	52 ms	17672 KB	Output is correct
52	Correct	53 ms	17672 KB	Output is correct
53	Correct	182 ms	17672 KB	Output is correct
54	Execution timed out	1050 ms	17672 KB	Time limit exceeded

답안 #84270

Compilation message

Subtask #1 30.0 / 30.0

Subtask #2 35.0 / 70.0

Subtask #1
30.0 / 30.0

Subtask #2
35.0 / 70.0