답안 #442735

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
442735	2021-07-08T19:45:54 Z	dutch	Graph (BOI20_graph)	C++17	100 / 100	203 ms	27160 KB

Graph

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN = 1e5;
double EPS = 1e-8;

vector<pair<int, bool>> g[MAXN];
int n, m, c[MAXN];
double x = 1e18, r[MAXN];
bool s[MAXN], vis[MAXN], ok = 1;
vector<int> comp;

void dfs(int u){
	vis[u] = 1; comp.push_back(u);
	for(auto &[v, w] : g[u]){
		if(!vis[v]){
			s[v] = !s[u];
			c[v] = (2 - (int)w) - c[u];
			dfs(v);
		}else if(s[u] == s[v])
			x = ((2 - (int)w) - c[u] - c[v]) / (s[u] ? -2.0 : 2.0);
	}
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	while(m--){
		int u, v, w; cin >> u >> v >> w;
		--u, --v;
		g[u].emplace_back(v, w&1);
		g[v].emplace_back(u, w&1);
	}
	for(int z=0; z<n && ok; ++z){
		if(vis[z]) continue;
		comp.clear(), x = 1e18, dfs(z);
		if(x > 1e17){
			vector<int> v;
			for(int i : comp) v.push_back(s[i] ? c[i] : -c[i]);
			sort(v.begin(), v.end());
			x = v[(int)v.size()/2];
		}
		for(int i : comp) r[i] = (c[i] + (s[i] ? -x : x));
	}
	for(int u=0; u<n; ++u)
		for(auto &[v, w] : g[u])
			ok = ok && abs((2 - (int)w) - r[u] - r[v]) < EPS;

	if(!ok) cout << "NO\n";
	else{
		cout << "YES\n";
		cout << setprecision(1) << fixed;
		for(int i=0; i<n; ++i) cout << r[i] << ' ';
	}
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2636 KB	answer = YES
2	Correct	2 ms	2672 KB	answer = YES
3	Correct	2 ms	2636 KB	answer = YES
4	Correct	2 ms	2636 KB	answer = NO
5	Correct	2 ms	2668 KB	answer = YES
6	Correct	2 ms	2636 KB	answer = YES
7	Correct	2 ms	2636 KB	answer = YES
8	Correct	2 ms	2636 KB	answer = YES
9	Correct	2 ms	2636 KB	answer = NO
10	Correct	2 ms	2636 KB	answer = YES
11	Correct	2 ms	2596 KB	answer = YES
12	Correct	2 ms	2636 KB	answer = NO
13	Correct	2 ms	2636 KB	answer = YES
14	Correct	2 ms	2636 KB	answer = YES
15	Correct	2 ms	2636 KB	answer = YES
16	Correct	2 ms	2636 KB	answer = YES
17	Correct	2 ms	2636 KB	answer = YES
18	Correct	2 ms	2672 KB	answer = YES
19	Correct	2 ms	2636 KB	answer = YES
20	Correct	2 ms	2636 KB	answer = YES
21	Correct	2 ms	2672 KB	answer = YES
22	Correct	2 ms	2636 KB	answer = NO
23	Correct	2 ms	2636 KB	answer = NO

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2636 KB	answer = YES
2	Correct	2 ms	2672 KB	answer = YES
3	Correct	2 ms	2636 KB	answer = YES
4	Correct	2 ms	2636 KB	answer = NO
5	Correct	2 ms	2668 KB	answer = YES
6	Correct	2 ms	2636 KB	answer = YES
7	Correct	2 ms	2636 KB	answer = YES
8	Correct	2 ms	2636 KB	answer = YES
9	Correct	2 ms	2636 KB	answer = NO
10	Correct	2 ms	2636 KB	answer = YES
11	Correct	2 ms	2596 KB	answer = YES
12	Correct	2 ms	2636 KB	answer = NO
13	Correct	2 ms	2636 KB	answer = YES
14	Correct	2 ms	2636 KB	answer = YES
15	Correct	2 ms	2636 KB	answer = YES
16	Correct	2 ms	2636 KB	answer = YES
17	Correct	2 ms	2636 KB	answer = YES
18	Correct	2 ms	2672 KB	answer = YES
19	Correct	2 ms	2636 KB	answer = YES
20	Correct	2 ms	2636 KB	answer = YES
21	Correct	2 ms	2672 KB	answer = YES
22	Correct	2 ms	2636 KB	answer = NO
23	Correct	2 ms	2636 KB	answer = NO
24	Correct	2 ms	2636 KB	answer = YES
25	Correct	2 ms	2636 KB	answer = YES
26	Correct	2 ms	2636 KB	answer = YES
27	Correct	2 ms	2668 KB	answer = YES
28	Correct	2 ms	2636 KB	answer = YES
29	Correct	2 ms	2636 KB	answer = YES
30	Correct	2 ms	2672 KB	answer = NO
31	Correct	2 ms	2636 KB	answer = YES
32	Correct	2 ms	2636 KB	answer = YES
33	Correct	2 ms	2636 KB	answer = YES
34	Correct	2 ms	2636 KB	answer = YES
35	Correct	2 ms	2636 KB	answer = YES
36	Correct	2 ms	2636 KB	answer = YES

Subtask #3
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2636 KB	answer = YES
2	Correct	2 ms	2672 KB	answer = YES
3	Correct	2 ms	2636 KB	answer = YES
4	Correct	2 ms	2636 KB	answer = NO
5	Correct	2 ms	2668 KB	answer = YES
6	Correct	2 ms	2636 KB	answer = YES
7	Correct	2 ms	2636 KB	answer = YES
8	Correct	2 ms	2636 KB	answer = YES
9	Correct	2 ms	2636 KB	answer = NO
10	Correct	2 ms	2636 KB	answer = YES
11	Correct	2 ms	2596 KB	answer = YES
12	Correct	2 ms	2636 KB	answer = NO
13	Correct	2 ms	2636 KB	answer = YES
14	Correct	2 ms	2636 KB	answer = YES
15	Correct	2 ms	2636 KB	answer = YES
16	Correct	2 ms	2636 KB	answer = YES
17	Correct	2 ms	2636 KB	answer = YES
18	Correct	2 ms	2672 KB	answer = YES
19	Correct	2 ms	2636 KB	answer = YES
20	Correct	2 ms	2636 KB	answer = YES
21	Correct	2 ms	2672 KB	answer = YES
22	Correct	2 ms	2636 KB	answer = NO
23	Correct	2 ms	2636 KB	answer = NO
24	Correct	2 ms	2636 KB	answer = YES
25	Correct	2 ms	2636 KB	answer = YES
26	Correct	2 ms	2636 KB	answer = YES
27	Correct	2 ms	2668 KB	answer = YES
28	Correct	2 ms	2636 KB	answer = YES
29	Correct	2 ms	2636 KB	answer = YES
30	Correct	2 ms	2672 KB	answer = NO
31	Correct	2 ms	2636 KB	answer = YES
32	Correct	2 ms	2636 KB	answer = YES
33	Correct	2 ms	2636 KB	answer = YES
34	Correct	2 ms	2636 KB	answer = YES
35	Correct	2 ms	2636 KB	answer = YES
36	Correct	2 ms	2636 KB	answer = YES
37	Correct	3 ms	2636 KB	answer = YES
38	Correct	2 ms	2636 KB	answer = YES
39	Correct	2 ms	2636 KB	answer = YES
40	Correct	3 ms	2764 KB	answer = YES
41	Correct	2 ms	2764 KB	answer = NO
42	Correct	3 ms	2764 KB	answer = YES
43	Correct	3 ms	2764 KB	answer = YES
44	Correct	3 ms	2780 KB	answer = YES
45	Correct	3 ms	2764 KB	answer = YES
46	Correct	2 ms	2636 KB	answer = YES
47	Correct	3 ms	2764 KB	answer = YES
48	Correct	3 ms	2764 KB	answer = YES

Subtask #4
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2636 KB	answer = YES
2	Correct	2 ms	2672 KB	answer = YES
3	Correct	2 ms	2636 KB	answer = YES
4	Correct	2 ms	2636 KB	answer = NO
5	Correct	2 ms	2668 KB	answer = YES
6	Correct	2 ms	2636 KB	answer = YES
7	Correct	2 ms	2636 KB	answer = YES
8	Correct	2 ms	2636 KB	answer = YES
9	Correct	2 ms	2636 KB	answer = NO
10	Correct	2 ms	2636 KB	answer = YES
11	Correct	2 ms	2596 KB	answer = YES
12	Correct	2 ms	2636 KB	answer = NO
13	Correct	2 ms	2636 KB	answer = YES
14	Correct	2 ms	2636 KB	answer = YES
15	Correct	2 ms	2636 KB	answer = YES
16	Correct	2 ms	2636 KB	answer = YES
17	Correct	2 ms	2636 KB	answer = YES
18	Correct	2 ms	2672 KB	answer = YES
19	Correct	2 ms	2636 KB	answer = YES
20	Correct	2 ms	2636 KB	answer = YES
21	Correct	2 ms	2672 KB	answer = YES
22	Correct	2 ms	2636 KB	answer = NO
23	Correct	2 ms	2636 KB	answer = NO
24	Correct	2 ms	2636 KB	answer = YES
25	Correct	2 ms	2636 KB	answer = YES
26	Correct	2 ms	2636 KB	answer = YES
27	Correct	2 ms	2668 KB	answer = YES
28	Correct	2 ms	2636 KB	answer = YES
29	Correct	2 ms	2636 KB	answer = YES
30	Correct	2 ms	2672 KB	answer = NO
31	Correct	2 ms	2636 KB	answer = YES
32	Correct	2 ms	2636 KB	answer = YES
33	Correct	2 ms	2636 KB	answer = YES
34	Correct	2 ms	2636 KB	answer = YES
35	Correct	2 ms	2636 KB	answer = YES
36	Correct	2 ms	2636 KB	answer = YES
37	Correct	3 ms	2636 KB	answer = YES
38	Correct	2 ms	2636 KB	answer = YES
39	Correct	2 ms	2636 KB	answer = YES
40	Correct	3 ms	2764 KB	answer = YES
41	Correct	2 ms	2764 KB	answer = NO
42	Correct	3 ms	2764 KB	answer = YES
43	Correct	3 ms	2764 KB	answer = YES
44	Correct	3 ms	2780 KB	answer = YES
45	Correct	3 ms	2764 KB	answer = YES
46	Correct	2 ms	2636 KB	answer = YES
47	Correct	3 ms	2764 KB	answer = YES
48	Correct	3 ms	2764 KB	answer = YES
49	Correct	11 ms	3740 KB	answer = YES
50	Correct	16 ms	4056 KB	answer = YES
51	Correct	16 ms	4036 KB	answer = YES
52	Correct	7 ms	4092 KB	answer = NO
53	Correct	3 ms	2764 KB	answer = YES
54	Correct	4 ms	2892 KB	answer = YES
55	Correct	6 ms	3148 KB	answer = YES
56	Correct	11 ms	3708 KB	answer = YES
57	Correct	11 ms	3580 KB	answer = YES
58	Correct	10 ms	3532 KB	answer = YES
59	Correct	10 ms	3516 KB	answer = YES
60	Correct	12 ms	3680 KB	answer = YES
61	Correct	7 ms	3148 KB	answer = YES
62	Correct	80 ms	14916 KB	answer = NO
63	Correct	85 ms	14888 KB	answer = YES
64	Correct	78 ms	14948 KB	answer = NO
65	Correct	81 ms	14960 KB	answer = YES
66	Correct	4 ms	2764 KB	answer = YES

Subtask #5
42.0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2636 KB	answer = YES
2	Correct	2 ms	2672 KB	answer = YES
3	Correct	2 ms	2636 KB	answer = YES
4	Correct	2 ms	2636 KB	answer = NO
5	Correct	2 ms	2668 KB	answer = YES
6	Correct	2 ms	2636 KB	answer = YES
7	Correct	2 ms	2636 KB	answer = YES
8	Correct	2 ms	2636 KB	answer = YES
9	Correct	2 ms	2636 KB	answer = NO
10	Correct	2 ms	2636 KB	answer = YES
11	Correct	2 ms	2596 KB	answer = YES
12	Correct	2 ms	2636 KB	answer = NO
13	Correct	2 ms	2636 KB	answer = YES
14	Correct	2 ms	2636 KB	answer = YES
15	Correct	2 ms	2636 KB	answer = YES
16	Correct	2 ms	2636 KB	answer = YES
17	Correct	2 ms	2636 KB	answer = YES
18	Correct	2 ms	2672 KB	answer = YES
19	Correct	2 ms	2636 KB	answer = YES
20	Correct	2 ms	2636 KB	answer = YES
21	Correct	2 ms	2672 KB	answer = YES
22	Correct	2 ms	2636 KB	answer = NO
23	Correct	2 ms	2636 KB	answer = NO
24	Correct	2 ms	2636 KB	answer = YES
25	Correct	2 ms	2636 KB	answer = YES
26	Correct	2 ms	2636 KB	answer = YES
27	Correct	2 ms	2668 KB	answer = YES
28	Correct	2 ms	2636 KB	answer = YES
29	Correct	2 ms	2636 KB	answer = YES
30	Correct	2 ms	2672 KB	answer = NO
31	Correct	2 ms	2636 KB	answer = YES
32	Correct	2 ms	2636 KB	answer = YES
33	Correct	2 ms	2636 KB	answer = YES
34	Correct	2 ms	2636 KB	answer = YES
35	Correct	2 ms	2636 KB	answer = YES
36	Correct	2 ms	2636 KB	answer = YES
37	Correct	3 ms	2636 KB	answer = YES
38	Correct	2 ms	2636 KB	answer = YES
39	Correct	2 ms	2636 KB	answer = YES
40	Correct	3 ms	2764 KB	answer = YES
41	Correct	2 ms	2764 KB	answer = NO
42	Correct	3 ms	2764 KB	answer = YES
43	Correct	3 ms	2764 KB	answer = YES
44	Correct	3 ms	2780 KB	answer = YES
45	Correct	3 ms	2764 KB	answer = YES
46	Correct	2 ms	2636 KB	answer = YES
47	Correct	3 ms	2764 KB	answer = YES
48	Correct	3 ms	2764 KB	answer = YES
49	Correct	11 ms	3740 KB	answer = YES
50	Correct	16 ms	4056 KB	answer = YES
51	Correct	16 ms	4036 KB	answer = YES
52	Correct	7 ms	4092 KB	answer = NO
53	Correct	3 ms	2764 KB	answer = YES
54	Correct	4 ms	2892 KB	answer = YES
55	Correct	6 ms	3148 KB	answer = YES
56	Correct	11 ms	3708 KB	answer = YES
57	Correct	11 ms	3580 KB	answer = YES
58	Correct	10 ms	3532 KB	answer = YES
59	Correct	10 ms	3516 KB	answer = YES
60	Correct	12 ms	3680 KB	answer = YES
61	Correct	7 ms	3148 KB	answer = YES
62	Correct	80 ms	14916 KB	answer = NO
63	Correct	85 ms	14888 KB	answer = YES
64	Correct	78 ms	14948 KB	answer = NO
65	Correct	81 ms	14960 KB	answer = YES
66	Correct	4 ms	2764 KB	answer = YES
67	Correct	117 ms	19712 KB	answer = YES
68	Correct	91 ms	19896 KB	answer = YES
69	Correct	90 ms	19584 KB	answer = YES
70	Correct	132 ms	27160 KB	answer = YES
71	Correct	91 ms	19696 KB	answer = YES
72	Correct	113 ms	12476 KB	answer = YES
73	Correct	107 ms	12248 KB	answer = YES
74	Correct	72 ms	12736 KB	answer = YES
75	Correct	42 ms	12460 KB	answer = NO
76	Correct	13 ms	3944 KB	answer = YES
77	Correct	28 ms	5128 KB	answer = YES
78	Correct	44 ms	6936 KB	answer = YES
79	Correct	91 ms	11192 KB	answer = YES
80	Correct	73 ms	12688 KB	answer = YES
81	Correct	54 ms	15444 KB	answer = NO
82	Correct	115 ms	18968 KB	answer = YES
83	Correct	165 ms	20304 KB	answer = YES
84	Correct	129 ms	20352 KB	answer = YES
85	Correct	117 ms	19768 KB	answer = YES
86	Correct	97 ms	19632 KB	answer = YES
87	Correct	93 ms	14224 KB	answer = NO
88	Correct	170 ms	15192 KB	answer = YES
89	Correct	103 ms	10820 KB	answer = YES
90	Correct	101 ms	10864 KB	answer = YES
91	Correct	145 ms	11336 KB	answer = YES
92	Correct	50 ms	7424 KB	answer = YES
93	Correct	48 ms	7412 KB	answer = YES
94	Correct	78 ms	20376 KB	answer = NO
95	Correct	63 ms	10968 KB	answer = NO
96	Correct	203 ms	23352 KB	answer = YES
97	Correct	49 ms	19768 KB	answer = NO

답안 #442735

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 12.0 / 12.0

Subtask #3 17.0 / 17.0

Subtask #4 24.0 / 24.0

Subtask #5 42.0 / 42.0

Subtask #1
5.0 / 5.0

Subtask #2
12.0 / 12.0

Subtask #3
17.0 / 17.0

Subtask #4
24.0 / 24.0

Subtask #5
42.0 / 42.0