답안 #855666

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
855666	2023-10-01T16:12:07 Z	Trisanu_Das	Graph (BOI20_graph)	C++17	100 / 100	110 ms	27296 KB

Graph

#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define int long long
 
double EPS = 1e-8;
 
vector<pair<int, bool>> adj[100000];
int n, m, c[100000];
double x = 1e18, ans[100000];
bool s[100000], vis[100000], ok = true;
vector<int> comp;
 
void dfs(int u){
	vis[u] = 1; comp.push_back(u);
	for(auto &[v, w] : adj[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(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	while(m--){
		int u, v, w; cin >> u >> v >> w;
		--u, --v;
		adj[u].emplace_back(v, w & 1);
		adj[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) ans[i] = (c[i] + (s[i] ? -x : x));
	}
	for(int u = 0; u < n; u++) for(auto &[v, w] : adj[u]) ok = ok && (abs((2 - (int)w) - ans[u] - ans[v]) < EPS);
	if(!ok) cout << "NO\n";
	else{
		cout << "YES\n";
		cout << setprecision(1) << fixed;
		for(int i = 0; i < n; i++) cout << ans[i] << ' ';
	}
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4188 KB	answer = YES
2	Correct	1 ms	4400 KB	answer = YES
3	Correct	1 ms	4188 KB	answer = YES
4	Correct	1 ms	4392 KB	answer = NO
5	Correct	2 ms	4444 KB	answer = YES
6	Correct	1 ms	4188 KB	answer = YES
7	Correct	2 ms	4188 KB	answer = YES
8	Correct	2 ms	4184 KB	answer = YES
9	Correct	2 ms	4440 KB	answer = NO
10	Correct	1 ms	4188 KB	answer = YES
11	Correct	1 ms	4188 KB	answer = YES
12	Correct	1 ms	4188 KB	answer = NO
13	Correct	1 ms	4188 KB	answer = YES
14	Correct	1 ms	4188 KB	answer = YES
15	Correct	1 ms	4396 KB	answer = YES
16	Correct	1 ms	4188 KB	answer = YES
17	Correct	1 ms	4188 KB	answer = YES
18	Correct	2 ms	4188 KB	answer = YES
19	Correct	1 ms	4184 KB	answer = YES
20	Correct	1 ms	4188 KB	answer = YES
21	Correct	1 ms	4188 KB	answer = YES
22	Correct	2 ms	4188 KB	answer = NO
23	Correct	1 ms	4188 KB	answer = NO

Subtask #2
12.0 / 12.0

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

Subtask #3
17.0 / 17.0

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

Subtask #4
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4188 KB	answer = YES
2	Correct	1 ms	4400 KB	answer = YES
3	Correct	1 ms	4188 KB	answer = YES
4	Correct	1 ms	4392 KB	answer = NO
5	Correct	2 ms	4444 KB	answer = YES
6	Correct	1 ms	4188 KB	answer = YES
7	Correct	2 ms	4188 KB	answer = YES
8	Correct	2 ms	4184 KB	answer = YES
9	Correct	2 ms	4440 KB	answer = NO
10	Correct	1 ms	4188 KB	answer = YES
11	Correct	1 ms	4188 KB	answer = YES
12	Correct	1 ms	4188 KB	answer = NO
13	Correct	1 ms	4188 KB	answer = YES
14	Correct	1 ms	4188 KB	answer = YES
15	Correct	1 ms	4396 KB	answer = YES
16	Correct	1 ms	4188 KB	answer = YES
17	Correct	1 ms	4188 KB	answer = YES
18	Correct	2 ms	4188 KB	answer = YES
19	Correct	1 ms	4184 KB	answer = YES
20	Correct	1 ms	4188 KB	answer = YES
21	Correct	1 ms	4188 KB	answer = YES
22	Correct	2 ms	4188 KB	answer = NO
23	Correct	1 ms	4188 KB	answer = NO
24	Correct	2 ms	4392 KB	answer = YES
25	Correct	1 ms	4188 KB	answer = YES
26	Correct	1 ms	4188 KB	answer = YES
27	Correct	1 ms	4188 KB	answer = YES
28	Correct	2 ms	4188 KB	answer = YES
29	Correct	1 ms	4188 KB	answer = YES
30	Correct	2 ms	4188 KB	answer = NO
31	Correct	1 ms	4188 KB	answer = YES
32	Correct	1 ms	4184 KB	answer = YES
33	Correct	1 ms	4184 KB	answer = YES
34	Correct	2 ms	4188 KB	answer = YES
35	Correct	1 ms	4188 KB	answer = YES
36	Correct	2 ms	4188 KB	answer = YES
37	Correct	1 ms	4188 KB	answer = YES
38	Correct	1 ms	4396 KB	answer = YES
39	Correct	2 ms	4444 KB	answer = YES
40	Correct	2 ms	4444 KB	answer = YES
41	Correct	1 ms	4444 KB	answer = NO
42	Correct	2 ms	4444 KB	answer = YES
43	Correct	2 ms	4444 KB	answer = YES
44	Correct	2 ms	4444 KB	answer = YES
45	Correct	2 ms	4444 KB	answer = YES
46	Correct	2 ms	4440 KB	answer = YES
47	Correct	2 ms	4444 KB	answer = YES
48	Correct	2 ms	4444 KB	answer = YES
49	Correct	7 ms	5208 KB	answer = YES
50	Correct	8 ms	5472 KB	answer = YES
51	Correct	7 ms	5724 KB	answer = YES
52	Correct	4 ms	5724 KB	answer = NO
53	Correct	2 ms	4444 KB	answer = YES
54	Correct	3 ms	4444 KB	answer = YES
55	Correct	4 ms	4700 KB	answer = YES
56	Correct	7 ms	5212 KB	answer = YES
57	Correct	7 ms	4956 KB	answer = YES
58	Correct	7 ms	4956 KB	answer = YES
59	Correct	7 ms	4952 KB	answer = YES
60	Correct	7 ms	5212 KB	answer = YES
61	Correct	4 ms	4700 KB	answer = YES
62	Correct	46 ms	16332 KB	answer = NO
63	Correct	46 ms	16468 KB	answer = YES
64	Correct	46 ms	16564 KB	answer = NO
65	Correct	47 ms	16476 KB	answer = YES
66	Correct	3 ms	4440 KB	answer = YES

Subtask #5
42.0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4188 KB	answer = YES
2	Correct	1 ms	4400 KB	answer = YES
3	Correct	1 ms	4188 KB	answer = YES
4	Correct	1 ms	4392 KB	answer = NO
5	Correct	2 ms	4444 KB	answer = YES
6	Correct	1 ms	4188 KB	answer = YES
7	Correct	2 ms	4188 KB	answer = YES
8	Correct	2 ms	4184 KB	answer = YES
9	Correct	2 ms	4440 KB	answer = NO
10	Correct	1 ms	4188 KB	answer = YES
11	Correct	1 ms	4188 KB	answer = YES
12	Correct	1 ms	4188 KB	answer = NO
13	Correct	1 ms	4188 KB	answer = YES
14	Correct	1 ms	4188 KB	answer = YES
15	Correct	1 ms	4396 KB	answer = YES
16	Correct	1 ms	4188 KB	answer = YES
17	Correct	1 ms	4188 KB	answer = YES
18	Correct	2 ms	4188 KB	answer = YES
19	Correct	1 ms	4184 KB	answer = YES
20	Correct	1 ms	4188 KB	answer = YES
21	Correct	1 ms	4188 KB	answer = YES
22	Correct	2 ms	4188 KB	answer = NO
23	Correct	1 ms	4188 KB	answer = NO
24	Correct	2 ms	4392 KB	answer = YES
25	Correct	1 ms	4188 KB	answer = YES
26	Correct	1 ms	4188 KB	answer = YES
27	Correct	1 ms	4188 KB	answer = YES
28	Correct	2 ms	4188 KB	answer = YES
29	Correct	1 ms	4188 KB	answer = YES
30	Correct	2 ms	4188 KB	answer = NO
31	Correct	1 ms	4188 KB	answer = YES
32	Correct	1 ms	4184 KB	answer = YES
33	Correct	1 ms	4184 KB	answer = YES
34	Correct	2 ms	4188 KB	answer = YES
35	Correct	1 ms	4188 KB	answer = YES
36	Correct	2 ms	4188 KB	answer = YES
37	Correct	1 ms	4188 KB	answer = YES
38	Correct	1 ms	4396 KB	answer = YES
39	Correct	2 ms	4444 KB	answer = YES
40	Correct	2 ms	4444 KB	answer = YES
41	Correct	1 ms	4444 KB	answer = NO
42	Correct	2 ms	4444 KB	answer = YES
43	Correct	2 ms	4444 KB	answer = YES
44	Correct	2 ms	4444 KB	answer = YES
45	Correct	2 ms	4444 KB	answer = YES
46	Correct	2 ms	4440 KB	answer = YES
47	Correct	2 ms	4444 KB	answer = YES
48	Correct	2 ms	4444 KB	answer = YES
49	Correct	7 ms	5208 KB	answer = YES
50	Correct	8 ms	5472 KB	answer = YES
51	Correct	7 ms	5724 KB	answer = YES
52	Correct	4 ms	5724 KB	answer = NO
53	Correct	2 ms	4444 KB	answer = YES
54	Correct	3 ms	4444 KB	answer = YES
55	Correct	4 ms	4700 KB	answer = YES
56	Correct	7 ms	5212 KB	answer = YES
57	Correct	7 ms	4956 KB	answer = YES
58	Correct	7 ms	4956 KB	answer = YES
59	Correct	7 ms	4952 KB	answer = YES
60	Correct	7 ms	5212 KB	answer = YES
61	Correct	4 ms	4700 KB	answer = YES
62	Correct	46 ms	16332 KB	answer = NO
63	Correct	46 ms	16468 KB	answer = YES
64	Correct	46 ms	16564 KB	answer = NO
65	Correct	47 ms	16476 KB	answer = YES
66	Correct	3 ms	4440 KB	answer = YES
67	Correct	68 ms	20520 KB	answer = YES
68	Correct	65 ms	20680 KB	answer = YES
69	Correct	62 ms	19736 KB	answer = YES
70	Correct	89 ms	27296 KB	answer = YES
71	Correct	60 ms	19672 KB	answer = YES
72	Correct	66 ms	13244 KB	answer = YES
73	Correct	60 ms	12236 KB	answer = YES
74	Correct	45 ms	13268 KB	answer = YES
75	Correct	23 ms	13520 KB	answer = NO
76	Correct	8 ms	5468 KB	answer = YES
77	Correct	16 ms	6520 KB	answer = YES
78	Correct	27 ms	8168 KB	answer = YES
79	Correct	55 ms	12236 KB	answer = YES
80	Correct	47 ms	13528 KB	answer = YES
81	Correct	33 ms	15568 KB	answer = NO
82	Correct	74 ms	19404 KB	answer = YES
83	Correct	79 ms	20484 KB	answer = YES
84	Correct	81 ms	21188 KB	answer = YES
85	Correct	68 ms	20984 KB	answer = YES
86	Correct	65 ms	19656 KB	answer = YES
87	Correct	39 ms	14208 KB	answer = NO
88	Correct	80 ms	15304 KB	answer = YES
89	Correct	60 ms	10960 KB	answer = YES
90	Correct	60 ms	10832 KB	answer = YES
91	Correct	85 ms	11500 KB	answer = YES
92	Correct	32 ms	8312 KB	answer = YES
93	Correct	31 ms	8344 KB	answer = YES
94	Correct	58 ms	21136 KB	answer = NO
95	Correct	44 ms	11000 KB	answer = NO
96	Correct	110 ms	23560 KB	answer = YES
97	Correct	33 ms	20688 KB	answer = NO

답안 #855666

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