답안 #467332

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
467332	2021-08-22T16:20:49 Z	MVP_Harry	Graph (BOI20_graph)	C++17	100 / 100	193 ms	19944 KB

Graph

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define rep(i, m, n) for (int i = m; i <= n; i++)
#define per(i, m, n) for (int i = m; i >= n; i--)
#define sz(v) (int) v.size()
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second

const int maxn = 1e5 + 5;
const double eps = 1e-6;

int N, M, leader, impossible, cycle = 0;
int vis[maxn];
double a[maxn];
vector<pair<int, int> > G[maxn];
vector<int> pt;
pair<int, int> c[maxn];

void dfs1(int u, int par) {
	vis[u] = 2;
	for (auto node : G[u]) {
		int v = node.fi, x = node.se;
		if (v == par) continue;
		if (vis[v] == 2) {
			// consider c[u], c[v]
			if (c[u].se + c[v].se == 0) {
				if (c[u].fi + c[v].fi != x) impossible = 1;
				else continue;
			}
			cycle = 1;
			double val = (double) (x - c[u].fi - c[v].fi) / (c[u].se + c[v].se);
			if (a[leader] == INF) a[leader] = val;
			else {
				if (abs(a[leader] - val) > eps) impossible = 1;
			}
		} else {
			c[v] = mp(x - c[u].fi, -c[u].se);
			dfs1(v, u);
		}
	}
}

void dfs2(int u, int par) {
	vis[u] = 3;
	pt.push_back((-c[u].se) * c[u].fi);
	for (auto node : G[u]) {
		if (node.fi == par || vis[node.fi] == 3) continue;
		dfs2(node.fi, u);
	}
}

void dfs3(int u, int par) {
	vis[u] = 1;
	if (u != leader) a[u] = (double) c[u].fi + (double) c[u].se * a[leader];
	for (auto node : G[u]) {
		if (node.fi == par || vis[node.fi] == 1) continue;
		dfs3(node.fi, u);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N >> M;
	rep(i, 1, M) {
		int u, v, x;
		cin >> u >> v >> x;
		G[u].push_back(mp(v, x)), G[v].push_back(mp(u, x));
	}
	rep(i, 1, N) a[i] = INF;
	rep(i, 1, N) if (!vis[i]) {
		c[i] = mp(0, 1);
		leader = i, cycle = 0;
		dfs1(i, 0);
		if (impossible) {
			cout << "NO\n";
			return 0;
		}
		if (!cycle) {
			pt.clear();
			dfs2(i, 0);
			sort(all(pt));
			a[leader] = pt[(sz(pt) - 1) / 2];
		}
		dfs3(i, 0);
	}
	cout << "YES\n";
	rep(i, 1, N) cout << a[i] << " ";
	cout << "\n";
	return 0;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2636 KB	answer = YES
2	Correct	2 ms	2636 KB	answer = YES
3	Correct	2 ms	2636 KB	answer = YES
4	Correct	2 ms	2636 KB	answer = NO
5	Correct	2 ms	2636 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	2636 KB	answer = YES
12	Correct	2 ms	2636 KB	answer = NO
13	Correct	2 ms	2676 KB	answer = YES
14	Correct	2 ms	2636 KB	answer = YES
15	Correct	2 ms	2688 KB	answer = YES
16	Correct	2 ms	2636 KB	answer = YES
17	Correct	2 ms	2636 KB	answer = YES
18	Correct	2 ms	2636 KB	answer = YES
19	Correct	2 ms	2636 KB	answer = YES
20	Correct	2 ms	2636 KB	answer = YES
21	Correct	2 ms	2636 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	2636 KB	answer = YES
3	Correct	2 ms	2636 KB	answer = YES
4	Correct	2 ms	2636 KB	answer = NO
5	Correct	2 ms	2636 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	2636 KB	answer = YES
12	Correct	2 ms	2636 KB	answer = NO
13	Correct	2 ms	2676 KB	answer = YES
14	Correct	2 ms	2636 KB	answer = YES
15	Correct	2 ms	2688 KB	answer = YES
16	Correct	2 ms	2636 KB	answer = YES
17	Correct	2 ms	2636 KB	answer = YES
18	Correct	2 ms	2636 KB	answer = YES
19	Correct	2 ms	2636 KB	answer = YES
20	Correct	2 ms	2636 KB	answer = YES
21	Correct	2 ms	2636 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	2680 KB	answer = YES
28	Correct	2 ms	2636 KB	answer = YES
29	Correct	2 ms	2676 KB	answer = YES
30	Correct	2 ms	2676 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	2636 KB	answer = YES
3	Correct	2 ms	2636 KB	answer = YES
4	Correct	2 ms	2636 KB	answer = NO
5	Correct	2 ms	2636 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	2636 KB	answer = YES
12	Correct	2 ms	2636 KB	answer = NO
13	Correct	2 ms	2676 KB	answer = YES
14	Correct	2 ms	2636 KB	answer = YES
15	Correct	2 ms	2688 KB	answer = YES
16	Correct	2 ms	2636 KB	answer = YES
17	Correct	2 ms	2636 KB	answer = YES
18	Correct	2 ms	2636 KB	answer = YES
19	Correct	2 ms	2636 KB	answer = YES
20	Correct	2 ms	2636 KB	answer = YES
21	Correct	2 ms	2636 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	2680 KB	answer = YES
28	Correct	2 ms	2636 KB	answer = YES
29	Correct	2 ms	2676 KB	answer = YES
30	Correct	2 ms	2676 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	2 ms	2636 KB	answer = YES
38	Correct	2 ms	2672 KB	answer = YES
39	Correct	2 ms	2636 KB	answer = YES
40	Correct	2 ms	2636 KB	answer = YES
41	Correct	2 ms	2636 KB	answer = NO
42	Correct	3 ms	2764 KB	answer = YES
43	Correct	3 ms	2636 KB	answer = YES
44	Correct	3 ms	2636 KB	answer = YES
45	Correct	3 ms	2636 KB	answer = YES
46	Correct	2 ms	2764 KB	answer = YES
47	Correct	4 ms	2636 KB	answer = YES
48	Correct	3 ms	2636 KB	answer = YES

Subtask #4
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2636 KB	answer = YES
2	Correct	2 ms	2636 KB	answer = YES
3	Correct	2 ms	2636 KB	answer = YES
4	Correct	2 ms	2636 KB	answer = NO
5	Correct	2 ms	2636 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	2636 KB	answer = YES
12	Correct	2 ms	2636 KB	answer = NO
13	Correct	2 ms	2676 KB	answer = YES
14	Correct	2 ms	2636 KB	answer = YES
15	Correct	2 ms	2688 KB	answer = YES
16	Correct	2 ms	2636 KB	answer = YES
17	Correct	2 ms	2636 KB	answer = YES
18	Correct	2 ms	2636 KB	answer = YES
19	Correct	2 ms	2636 KB	answer = YES
20	Correct	2 ms	2636 KB	answer = YES
21	Correct	2 ms	2636 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	2680 KB	answer = YES
28	Correct	2 ms	2636 KB	answer = YES
29	Correct	2 ms	2676 KB	answer = YES
30	Correct	2 ms	2676 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	2 ms	2636 KB	answer = YES
38	Correct	2 ms	2672 KB	answer = YES
39	Correct	2 ms	2636 KB	answer = YES
40	Correct	2 ms	2636 KB	answer = YES
41	Correct	2 ms	2636 KB	answer = NO
42	Correct	3 ms	2764 KB	answer = YES
43	Correct	3 ms	2636 KB	answer = YES
44	Correct	3 ms	2636 KB	answer = YES
45	Correct	3 ms	2636 KB	answer = YES
46	Correct	2 ms	2764 KB	answer = YES
47	Correct	4 ms	2636 KB	answer = YES
48	Correct	3 ms	2636 KB	answer = YES
49	Correct	11 ms	3436 KB	answer = YES
50	Correct	14 ms	3580 KB	answer = YES
51	Correct	11 ms	3788 KB	answer = YES
52	Correct	6 ms	3588 KB	answer = NO
53	Correct	3 ms	2636 KB	answer = YES
54	Correct	4 ms	2764 KB	answer = YES
55	Correct	6 ms	3092 KB	answer = YES
56	Correct	11 ms	3472 KB	answer = YES
57	Correct	11 ms	3324 KB	answer = YES
58	Correct	11 ms	3276 KB	answer = YES
59	Correct	10 ms	3276 KB	answer = YES
60	Correct	11 ms	3404 KB	answer = YES
61	Correct	6 ms	3020 KB	answer = YES
62	Correct	73 ms	10176 KB	answer = NO
63	Correct	91 ms	10244 KB	answer = YES
64	Correct	72 ms	10124 KB	answer = NO
65	Correct	78 ms	10180 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	2636 KB	answer = YES
3	Correct	2 ms	2636 KB	answer = YES
4	Correct	2 ms	2636 KB	answer = NO
5	Correct	2 ms	2636 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	2636 KB	answer = YES
12	Correct	2 ms	2636 KB	answer = NO
13	Correct	2 ms	2676 KB	answer = YES
14	Correct	2 ms	2636 KB	answer = YES
15	Correct	2 ms	2688 KB	answer = YES
16	Correct	2 ms	2636 KB	answer = YES
17	Correct	2 ms	2636 KB	answer = YES
18	Correct	2 ms	2636 KB	answer = YES
19	Correct	2 ms	2636 KB	answer = YES
20	Correct	2 ms	2636 KB	answer = YES
21	Correct	2 ms	2636 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	2680 KB	answer = YES
28	Correct	2 ms	2636 KB	answer = YES
29	Correct	2 ms	2676 KB	answer = YES
30	Correct	2 ms	2676 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	2 ms	2636 KB	answer = YES
38	Correct	2 ms	2672 KB	answer = YES
39	Correct	2 ms	2636 KB	answer = YES
40	Correct	2 ms	2636 KB	answer = YES
41	Correct	2 ms	2636 KB	answer = NO
42	Correct	3 ms	2764 KB	answer = YES
43	Correct	3 ms	2636 KB	answer = YES
44	Correct	3 ms	2636 KB	answer = YES
45	Correct	3 ms	2636 KB	answer = YES
46	Correct	2 ms	2764 KB	answer = YES
47	Correct	4 ms	2636 KB	answer = YES
48	Correct	3 ms	2636 KB	answer = YES
49	Correct	11 ms	3436 KB	answer = YES
50	Correct	14 ms	3580 KB	answer = YES
51	Correct	11 ms	3788 KB	answer = YES
52	Correct	6 ms	3588 KB	answer = NO
53	Correct	3 ms	2636 KB	answer = YES
54	Correct	4 ms	2764 KB	answer = YES
55	Correct	6 ms	3092 KB	answer = YES
56	Correct	11 ms	3472 KB	answer = YES
57	Correct	11 ms	3324 KB	answer = YES
58	Correct	11 ms	3276 KB	answer = YES
59	Correct	10 ms	3276 KB	answer = YES
60	Correct	11 ms	3404 KB	answer = YES
61	Correct	6 ms	3020 KB	answer = YES
62	Correct	73 ms	10176 KB	answer = NO
63	Correct	91 ms	10244 KB	answer = YES
64	Correct	72 ms	10124 KB	answer = NO
65	Correct	78 ms	10180 KB	answer = YES
66	Correct	4 ms	2764 KB	answer = YES
67	Correct	98 ms	16132 KB	answer = YES
68	Correct	94 ms	16016 KB	answer = YES
69	Correct	90 ms	15408 KB	answer = YES
70	Correct	131 ms	19944 KB	answer = YES
71	Correct	93 ms	15728 KB	answer = YES
72	Correct	120 ms	10340 KB	answer = YES
73	Correct	107 ms	9848 KB	answer = YES
74	Correct	66 ms	10180 KB	answer = YES
75	Correct	32 ms	10024 KB	answer = NO
76	Correct	13 ms	3532 KB	answer = YES
77	Correct	27 ms	4640 KB	answer = YES
78	Correct	46 ms	6068 KB	answer = YES
79	Correct	96 ms	9308 KB	answer = YES
80	Correct	73 ms	10584 KB	answer = YES
81	Correct	48 ms	12316 KB	answer = NO
82	Correct	107 ms	15216 KB	answer = YES
83	Correct	124 ms	15684 KB	answer = YES
84	Correct	141 ms	16120 KB	answer = YES
85	Correct	100 ms	16188 KB	answer = YES
86	Correct	93 ms	15572 KB	answer = YES
87	Correct	58 ms	10820 KB	answer = NO
88	Correct	127 ms	12204 KB	answer = YES
89	Correct	105 ms	9284 KB	answer = YES
90	Correct	105 ms	9488 KB	answer = YES
91	Correct	102 ms	9288 KB	answer = YES
92	Correct	52 ms	6344 KB	answer = YES
93	Correct	48 ms	6240 KB	answer = YES
94	Correct	62 ms	15260 KB	answer = NO
95	Correct	48 ms	9040 KB	answer = NO
96	Correct	193 ms	17560 KB	answer = YES
97	Correct	45 ms	15216 KB	answer = NO

답안 #467332

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