답안 #581677

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
581677	2022-06-23T03:05:28 Z	elpro123	Graph (BOI20_graph)	C++14	100 / 100	261 ms	17768 KB

Graph

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
int N, M, vistos[100005], datos[100005], con[100005];
double val[100005];
vector<pii> graph[100005];
vector<int> nds, elems;
int founda = 0, rip = 0;
double aval = 0;
 
void ripexit() {
	printf("NO\n");
	
}
 
void dfs(int x) {
	nds.push_back(x);
	vistos[x] = 1;
	for(pii p : graph[x]){
		int v = p.first, k = p.second;
		if(vistos[v]){
			if(datos[v] + datos[x]){
				double pval = (k - (con[v] + con[x]))/((double)(datos[v] + datos[x]));
				if(founda){ 
					if(abs(pval - aval) > 0) {//0.0000001
						rip = 1;
					}
				}else{
					founda = 1;
					aval = pval;
				}
			}else{
				if(con[v] + con[x] != k){
					rip = 1;
				}
			}
		}else{
			datos[v] = -datos[x];
			con[v] = k - con[x];
			dfs(v);
		}
	}
}
 
int main() {
	cin>>N>>M;
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin>>a>>b>>c;
		graph[a].push_back({ b, c });
		graph[b].push_back({ a, c });
	}
	for (int i = 1; i <= N; i++) {
		if (!vistos[i]) {
			founda = 0, rip = 0;
			datos[i] = 1;
			con[i] = 0;
			dfs(i);
			if (rip) {
				ripexit();
				return 0;
			}
			if (!founda) {
				elems.clear();
				for(int x : nds) {
					elems.push_back(con[x] * datos[x]);
				}
				sort(elems.begin(), elems.end());
				aval = -elems[elems.size()/2];
			}
			for (int x : nds) {
				val[x] = datos[x] * aval + con[x];
			}
			nds.clear();
		}
	}
	puts("YES");
	for(int i=1; i<=N; i++) {
		if(i == 1){
			cout<<val[i]<<" ";
		}else{
			cout<<val[i]<<" ";
		}
	} 
	cout<<"\n";
}

Subtask #1
5.0 / 5.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
17.0 / 17.0

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

Subtask #4
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2644 KB	answer = YES
2	Correct	2 ms	2644 KB	answer = YES
3	Correct	2 ms	2644 KB	answer = YES
4	Correct	1 ms	2644 KB	answer = NO
5	Correct	2 ms	2644 KB	answer = YES
6	Correct	2 ms	2644 KB	answer = YES
7	Correct	2 ms	2644 KB	answer = YES
8	Correct	2 ms	2644 KB	answer = YES
9	Correct	3 ms	2676 KB	answer = NO
10	Correct	2 ms	2644 KB	answer = YES
11	Correct	2 ms	2644 KB	answer = YES
12	Correct	2 ms	2644 KB	answer = NO
13	Correct	2 ms	2644 KB	answer = YES
14	Correct	2 ms	2644 KB	answer = YES
15	Correct	1 ms	2644 KB	answer = YES
16	Correct	2 ms	2644 KB	answer = YES
17	Correct	2 ms	2644 KB	answer = YES
18	Correct	2 ms	2644 KB	answer = YES
19	Correct	1 ms	2644 KB	answer = YES
20	Correct	2 ms	2644 KB	answer = YES
21	Correct	2 ms	2644 KB	answer = YES
22	Correct	1 ms	2644 KB	answer = NO
23	Correct	2 ms	2644 KB	answer = NO
24	Correct	2 ms	2644 KB	answer = YES
25	Correct	2 ms	2644 KB	answer = YES
26	Correct	2 ms	2644 KB	answer = YES
27	Correct	2 ms	2644 KB	answer = YES
28	Correct	2 ms	2644 KB	answer = YES
29	Correct	2 ms	2604 KB	answer = YES
30	Correct	1 ms	2644 KB	answer = NO
31	Correct	2 ms	2644 KB	answer = YES
32	Correct	2 ms	2644 KB	answer = YES
33	Correct	2 ms	2644 KB	answer = YES
34	Correct	2 ms	2644 KB	answer = YES
35	Correct	2 ms	2656 KB	answer = YES
36	Correct	2 ms	2680 KB	answer = YES
37	Correct	3 ms	2644 KB	answer = YES
38	Correct	2 ms	2644 KB	answer = YES
39	Correct	3 ms	2644 KB	answer = YES
40	Correct	3 ms	2644 KB	answer = YES
41	Correct	2 ms	2644 KB	answer = NO
42	Correct	3 ms	2644 KB	answer = YES
43	Correct	3 ms	2644 KB	answer = YES
44	Correct	3 ms	2644 KB	answer = YES
45	Correct	3 ms	2644 KB	answer = YES
46	Correct	3 ms	2584 KB	answer = YES
47	Correct	3 ms	2644 KB	answer = YES
48	Correct	3 ms	2644 KB	answer = YES
49	Correct	14 ms	3304 KB	answer = YES
50	Correct	14 ms	3676 KB	answer = YES
51	Correct	14 ms	3668 KB	answer = YES
52	Correct	9 ms	3540 KB	answer = NO
53	Correct	3 ms	2644 KB	answer = YES
54	Correct	5 ms	2772 KB	answer = YES
55	Correct	7 ms	3028 KB	answer = YES
56	Correct	14 ms	3284 KB	answer = YES
57	Correct	14 ms	3200 KB	answer = YES
58	Correct	12 ms	3260 KB	answer = YES
59	Correct	12 ms	3244 KB	answer = YES
60	Correct	16 ms	3240 KB	answer = YES
61	Correct	7 ms	2900 KB	answer = YES
62	Correct	145 ms	7908 KB	answer = NO
63	Correct	164 ms	7936 KB	answer = YES
64	Correct	155 ms	7920 KB	answer = NO
65	Correct	142 ms	7920 KB	answer = YES
66	Correct	4 ms	2772 KB	answer = YES

Subtask #5
42.0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2644 KB	answer = YES
2	Correct	2 ms	2644 KB	answer = YES
3	Correct	2 ms	2644 KB	answer = YES
4	Correct	1 ms	2644 KB	answer = NO
5	Correct	2 ms	2644 KB	answer = YES
6	Correct	2 ms	2644 KB	answer = YES
7	Correct	2 ms	2644 KB	answer = YES
8	Correct	2 ms	2644 KB	answer = YES
9	Correct	3 ms	2676 KB	answer = NO
10	Correct	2 ms	2644 KB	answer = YES
11	Correct	2 ms	2644 KB	answer = YES
12	Correct	2 ms	2644 KB	answer = NO
13	Correct	2 ms	2644 KB	answer = YES
14	Correct	2 ms	2644 KB	answer = YES
15	Correct	1 ms	2644 KB	answer = YES
16	Correct	2 ms	2644 KB	answer = YES
17	Correct	2 ms	2644 KB	answer = YES
18	Correct	2 ms	2644 KB	answer = YES
19	Correct	1 ms	2644 KB	answer = YES
20	Correct	2 ms	2644 KB	answer = YES
21	Correct	2 ms	2644 KB	answer = YES
22	Correct	1 ms	2644 KB	answer = NO
23	Correct	2 ms	2644 KB	answer = NO
24	Correct	2 ms	2644 KB	answer = YES
25	Correct	2 ms	2644 KB	answer = YES
26	Correct	2 ms	2644 KB	answer = YES
27	Correct	2 ms	2644 KB	answer = YES
28	Correct	2 ms	2644 KB	answer = YES
29	Correct	2 ms	2604 KB	answer = YES
30	Correct	1 ms	2644 KB	answer = NO
31	Correct	2 ms	2644 KB	answer = YES
32	Correct	2 ms	2644 KB	answer = YES
33	Correct	2 ms	2644 KB	answer = YES
34	Correct	2 ms	2644 KB	answer = YES
35	Correct	2 ms	2656 KB	answer = YES
36	Correct	2 ms	2680 KB	answer = YES
37	Correct	3 ms	2644 KB	answer = YES
38	Correct	2 ms	2644 KB	answer = YES
39	Correct	3 ms	2644 KB	answer = YES
40	Correct	3 ms	2644 KB	answer = YES
41	Correct	2 ms	2644 KB	answer = NO
42	Correct	3 ms	2644 KB	answer = YES
43	Correct	3 ms	2644 KB	answer = YES
44	Correct	3 ms	2644 KB	answer = YES
45	Correct	3 ms	2644 KB	answer = YES
46	Correct	3 ms	2584 KB	answer = YES
47	Correct	3 ms	2644 KB	answer = YES
48	Correct	3 ms	2644 KB	answer = YES
49	Correct	14 ms	3304 KB	answer = YES
50	Correct	14 ms	3676 KB	answer = YES
51	Correct	14 ms	3668 KB	answer = YES
52	Correct	9 ms	3540 KB	answer = NO
53	Correct	3 ms	2644 KB	answer = YES
54	Correct	5 ms	2772 KB	answer = YES
55	Correct	7 ms	3028 KB	answer = YES
56	Correct	14 ms	3284 KB	answer = YES
57	Correct	14 ms	3200 KB	answer = YES
58	Correct	12 ms	3260 KB	answer = YES
59	Correct	12 ms	3244 KB	answer = YES
60	Correct	16 ms	3240 KB	answer = YES
61	Correct	7 ms	2900 KB	answer = YES
62	Correct	145 ms	7908 KB	answer = NO
63	Correct	164 ms	7936 KB	answer = YES
64	Correct	155 ms	7920 KB	answer = NO
65	Correct	142 ms	7920 KB	answer = YES
66	Correct	4 ms	2772 KB	answer = YES
67	Correct	150 ms	15132 KB	answer = YES
68	Correct	126 ms	15056 KB	answer = YES
69	Correct	124 ms	14668 KB	answer = YES
70	Correct	204 ms	17768 KB	answer = YES
71	Correct	131 ms	14880 KB	answer = YES
72	Correct	148 ms	9396 KB	answer = YES
73	Correct	137 ms	8968 KB	answer = YES
74	Correct	96 ms	9692 KB	answer = YES
75	Correct	59 ms	8980 KB	answer = NO
76	Correct	16 ms	3536 KB	answer = YES
77	Correct	32 ms	4384 KB	answer = YES
78	Correct	57 ms	5640 KB	answer = YES
79	Correct	115 ms	8456 KB	answer = YES
80	Correct	90 ms	10004 KB	answer = YES
81	Correct	97 ms	10656 KB	answer = NO
82	Correct	143 ms	14384 KB	answer = YES
83	Correct	162 ms	14796 KB	answer = YES
84	Correct	160 ms	15128 KB	answer = YES
85	Correct	142 ms	15132 KB	answer = YES
86	Correct	122 ms	14740 KB	answer = YES
87	Correct	93 ms	9672 KB	answer = NO
88	Correct	167 ms	11064 KB	answer = YES
89	Correct	128 ms	7920 KB	answer = YES
90	Correct	133 ms	7992 KB	answer = YES
91	Correct	173 ms	7988 KB	answer = YES
92	Correct	67 ms	5988 KB	answer = YES
93	Correct	62 ms	5908 KB	answer = YES
94	Correct	146 ms	13628 KB	answer = NO
95	Correct	103 ms	7620 KB	answer = NO
96	Correct	261 ms	15460 KB	answer = YES
97	Correct	84 ms	13696 KB	answer = NO

답안 #581677

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