# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
745424 | 2023-05-20T04:54:24 Z | MilosMilutinovic | Graph (BOI20_graph) | C++14 | 144 ms | 23124 KB |
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 10; int n, m, coeff[N], delta[N]; double ans[N], val; vector<pair<int, int>> g[N]; vector<int> comp; bool ok = true, found, was[N]; void dfs(int x) { was[x] = true; comp.push_back(x); for (auto& p : g[x]) { int y = p.first; int w = p.second; if (was[y]) { if (-coeff[y] == coeff[x]) { ok = (ok & ((w - delta[y]) == delta[x])); } else { found = true; val = (w - delta[x] - delta[y]) * 1.0 / (coeff[y] + coeff[x]); } continue; } coeff[y] = -coeff[x]; delta[y] = w - delta[x]; dfs(y); } } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); g[a].emplace_back(b, c); g[b].emplace_back(a, c); } for (int i = 1; i <= n; i++) if (!was[i]) { coeff[i] = 1; delta[i] = 0; comp.clear(); found = false; dfs(i); if (!ok) break; if (found) { for (int x : comp) ans[x] = val * coeff[x] + delta[x]; } else { vector<int> f; for (int x : comp) f.push_back(delta[x] * coeff[x]); sort(f.begin(), f.end()); val = -f[(int) f.size() / 2]; for (int x : comp) ans[x] = val * coeff[x] + delta[x]; } } for (int i = 1; i <= n; i++) { for (auto& p : g[i]) { if (ans[i] + ans[p.first] != p.second * 1.0) ok = false; } } if (!ok) { printf("NO"); return 0; } printf("YES\n"); for (int i = 1; i <= n; i++) printf("%0.5lf ", ans[i]); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4948 KB | answer = YES |
2 | Correct | 3 ms | 4948 KB | answer = YES |
3 | Correct | 3 ms | 5012 KB | answer = YES |
4 | Correct | 3 ms | 4948 KB | answer = NO |
5 | Correct | 3 ms | 4948 KB | answer = YES |
6 | Correct | 3 ms | 4948 KB | answer = YES |
7 | Correct | 3 ms | 4948 KB | answer = YES |
8 | Correct | 3 ms | 4948 KB | answer = YES |
9 | Correct | 3 ms | 5020 KB | answer = NO |
10 | Correct | 2 ms | 4948 KB | answer = YES |
11 | Correct | 3 ms | 4948 KB | answer = YES |
12 | Correct | 3 ms | 5076 KB | answer = NO |
13 | Correct | 4 ms | 4948 KB | answer = YES |
14 | Correct | 3 ms | 4948 KB | answer = YES |
15 | Correct | 3 ms | 5012 KB | answer = YES |
16 | Correct | 3 ms | 5012 KB | answer = YES |
17 | Correct | 3 ms | 5016 KB | answer = YES |
18 | Correct | 2 ms | 4948 KB | answer = YES |
19 | Correct | 3 ms | 4948 KB | answer = YES |
20 | Correct | 3 ms | 4948 KB | answer = YES |
21 | Correct | 3 ms | 4948 KB | answer = YES |
22 | Correct | 3 ms | 4948 KB | answer = NO |
23 | Correct | 3 ms | 4948 KB | answer = NO |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4948 KB | answer = YES |
2 | Correct | 3 ms | 4948 KB | answer = YES |
3 | Correct | 3 ms | 5012 KB | answer = YES |
4 | Correct | 3 ms | 4948 KB | answer = NO |
5 | Correct | 3 ms | 4948 KB | answer = YES |
6 | Correct | 3 ms | 4948 KB | answer = YES |
7 | Correct | 3 ms | 4948 KB | answer = YES |
8 | Correct | 3 ms | 4948 KB | answer = YES |
9 | Correct | 3 ms | 5020 KB | answer = NO |
10 | Correct | 2 ms | 4948 KB | answer = YES |
11 | Correct | 3 ms | 4948 KB | answer = YES |
12 | Correct | 3 ms | 5076 KB | answer = NO |
13 | Correct | 4 ms | 4948 KB | answer = YES |
14 | Correct | 3 ms | 4948 KB | answer = YES |
15 | Correct | 3 ms | 5012 KB | answer = YES |
16 | Correct | 3 ms | 5012 KB | answer = YES |
17 | Correct | 3 ms | 5016 KB | answer = YES |
18 | Correct | 2 ms | 4948 KB | answer = YES |
19 | Correct | 3 ms | 4948 KB | answer = YES |
20 | Correct | 3 ms | 4948 KB | answer = YES |
21 | Correct | 3 ms | 4948 KB | answer = YES |
22 | Correct | 3 ms | 4948 KB | answer = NO |
23 | Correct | 3 ms | 4948 KB | answer = NO |
24 | Correct | 3 ms | 5016 KB | answer = YES |
25 | Correct | 4 ms | 4948 KB | answer = YES |
26 | Correct | 3 ms | 4948 KB | answer = YES |
27 | Correct | 4 ms | 5016 KB | answer = YES |
28 | Correct | 3 ms | 4948 KB | answer = YES |
29 | Correct | 3 ms | 4948 KB | answer = YES |
30 | Correct | 3 ms | 5016 KB | answer = NO |
31 | Correct | 3 ms | 4948 KB | answer = YES |
32 | Correct | 3 ms | 5016 KB | answer = YES |
33 | Correct | 3 ms | 4948 KB | answer = YES |
34 | Correct | 3 ms | 4948 KB | answer = YES |
35 | Correct | 4 ms | 5016 KB | answer = YES |
36 | Correct | 3 ms | 4948 KB | answer = YES |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4948 KB | answer = YES |
2 | Correct | 3 ms | 4948 KB | answer = YES |
3 | Correct | 3 ms | 5012 KB | answer = YES |
4 | Correct | 3 ms | 4948 KB | answer = NO |
5 | Correct | 3 ms | 4948 KB | answer = YES |
6 | Correct | 3 ms | 4948 KB | answer = YES |
7 | Correct | 3 ms | 4948 KB | answer = YES |
8 | Correct | 3 ms | 4948 KB | answer = YES |
9 | Correct | 3 ms | 5020 KB | answer = NO |
10 | Correct | 2 ms | 4948 KB | answer = YES |
11 | Correct | 3 ms | 4948 KB | answer = YES |
12 | Correct | 3 ms | 5076 KB | answer = NO |
13 | Correct | 4 ms | 4948 KB | answer = YES |
14 | Correct | 3 ms | 4948 KB | answer = YES |
15 | Correct | 3 ms | 5012 KB | answer = YES |
16 | Correct | 3 ms | 5012 KB | answer = YES |
17 | Correct | 3 ms | 5016 KB | answer = YES |
18 | Correct | 2 ms | 4948 KB | answer = YES |
19 | Correct | 3 ms | 4948 KB | answer = YES |
20 | Correct | 3 ms | 4948 KB | answer = YES |
21 | Correct | 3 ms | 4948 KB | answer = YES |
22 | Correct | 3 ms | 4948 KB | answer = NO |
23 | Correct | 3 ms | 4948 KB | answer = NO |
24 | Correct | 3 ms | 5016 KB | answer = YES |
25 | Correct | 4 ms | 4948 KB | answer = YES |
26 | Correct | 3 ms | 4948 KB | answer = YES |
27 | Correct | 4 ms | 5016 KB | answer = YES |
28 | Correct | 3 ms | 4948 KB | answer = YES |
29 | Correct | 3 ms | 4948 KB | answer = YES |
30 | Correct | 3 ms | 5016 KB | answer = NO |
31 | Correct | 3 ms | 4948 KB | answer = YES |
32 | Correct | 3 ms | 5016 KB | answer = YES |
33 | Correct | 3 ms | 4948 KB | answer = YES |
34 | Correct | 3 ms | 4948 KB | answer = YES |
35 | Correct | 4 ms | 5016 KB | answer = YES |
36 | Correct | 3 ms | 4948 KB | answer = YES |
37 | Correct | 3 ms | 4948 KB | answer = YES |
38 | Correct | 3 ms | 4948 KB | answer = YES |
39 | Correct | 3 ms | 4948 KB | answer = YES |
40 | Correct | 3 ms | 5076 KB | answer = YES |
41 | Correct | 3 ms | 5076 KB | answer = NO |
42 | Correct | 3 ms | 5020 KB | answer = YES |
43 | Correct | 4 ms | 5080 KB | answer = YES |
44 | Correct | 4 ms | 5076 KB | answer = YES |
45 | Correct | 3 ms | 5016 KB | answer = YES |
46 | Correct | 3 ms | 4948 KB | answer = YES |
47 | Correct | 4 ms | 5004 KB | answer = YES |
48 | Correct | 4 ms | 5076 KB | answer = YES |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4948 KB | answer = YES |
2 | Correct | 3 ms | 4948 KB | answer = YES |
3 | Correct | 3 ms | 5012 KB | answer = YES |
4 | Correct | 3 ms | 4948 KB | answer = NO |
5 | Correct | 3 ms | 4948 KB | answer = YES |
6 | Correct | 3 ms | 4948 KB | answer = YES |
7 | Correct | 3 ms | 4948 KB | answer = YES |
8 | Correct | 3 ms | 4948 KB | answer = YES |
9 | Correct | 3 ms | 5020 KB | answer = NO |
10 | Correct | 2 ms | 4948 KB | answer = YES |
11 | Correct | 3 ms | 4948 KB | answer = YES |
12 | Correct | 3 ms | 5076 KB | answer = NO |
13 | Correct | 4 ms | 4948 KB | answer = YES |
14 | Correct | 3 ms | 4948 KB | answer = YES |
15 | Correct | 3 ms | 5012 KB | answer = YES |
16 | Correct | 3 ms | 5012 KB | answer = YES |
17 | Correct | 3 ms | 5016 KB | answer = YES |
18 | Correct | 2 ms | 4948 KB | answer = YES |
19 | Correct | 3 ms | 4948 KB | answer = YES |
20 | Correct | 3 ms | 4948 KB | answer = YES |
21 | Correct | 3 ms | 4948 KB | answer = YES |
22 | Correct | 3 ms | 4948 KB | answer = NO |
23 | Correct | 3 ms | 4948 KB | answer = NO |
24 | Correct | 3 ms | 5016 KB | answer = YES |
25 | Correct | 4 ms | 4948 KB | answer = YES |
26 | Correct | 3 ms | 4948 KB | answer = YES |
27 | Correct | 4 ms | 5016 KB | answer = YES |
28 | Correct | 3 ms | 4948 KB | answer = YES |
29 | Correct | 3 ms | 4948 KB | answer = YES |
30 | Correct | 3 ms | 5016 KB | answer = NO |
31 | Correct | 3 ms | 4948 KB | answer = YES |
32 | Correct | 3 ms | 5016 KB | answer = YES |
33 | Correct | 3 ms | 4948 KB | answer = YES |
34 | Correct | 3 ms | 4948 KB | answer = YES |
35 | Correct | 4 ms | 5016 KB | answer = YES |
36 | Correct | 3 ms | 4948 KB | answer = YES |
37 | Correct | 3 ms | 4948 KB | answer = YES |
38 | Correct | 3 ms | 4948 KB | answer = YES |
39 | Correct | 3 ms | 4948 KB | answer = YES |
40 | Correct | 3 ms | 5076 KB | answer = YES |
41 | Correct | 3 ms | 5076 KB | answer = NO |
42 | Correct | 3 ms | 5020 KB | answer = YES |
43 | Correct | 4 ms | 5080 KB | answer = YES |
44 | Correct | 4 ms | 5076 KB | answer = YES |
45 | Correct | 3 ms | 5016 KB | answer = YES |
46 | Correct | 3 ms | 4948 KB | answer = YES |
47 | Correct | 4 ms | 5004 KB | answer = YES |
48 | Correct | 4 ms | 5076 KB | answer = YES |
49 | Correct | 9 ms | 5844 KB | answer = YES |
50 | Correct | 10 ms | 6100 KB | answer = YES |
51 | Correct | 11 ms | 6180 KB | answer = YES |
52 | Correct | 7 ms | 5972 KB | answer = NO |
53 | Correct | 3 ms | 5076 KB | answer = YES |
54 | Correct | 5 ms | 5204 KB | answer = YES |
55 | Correct | 8 ms | 5460 KB | answer = YES |
56 | Correct | 12 ms | 5844 KB | answer = YES |
57 | Correct | 8 ms | 5668 KB | answer = YES |
58 | Correct | 8 ms | 5716 KB | answer = YES |
59 | Correct | 9 ms | 5668 KB | answer = YES |
60 | Correct | 11 ms | 5716 KB | answer = YES |
61 | Correct | 6 ms | 5324 KB | answer = YES |
62 | Correct | 68 ms | 12556 KB | answer = NO |
63 | Correct | 65 ms | 12604 KB | answer = YES |
64 | Correct | 61 ms | 12492 KB | answer = NO |
65 | Correct | 81 ms | 12612 KB | answer = YES |
66 | Correct | 4 ms | 5076 KB | answer = YES |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4948 KB | answer = YES |
2 | Correct | 3 ms | 4948 KB | answer = YES |
3 | Correct | 3 ms | 5012 KB | answer = YES |
4 | Correct | 3 ms | 4948 KB | answer = NO |
5 | Correct | 3 ms | 4948 KB | answer = YES |
6 | Correct | 3 ms | 4948 KB | answer = YES |
7 | Correct | 3 ms | 4948 KB | answer = YES |
8 | Correct | 3 ms | 4948 KB | answer = YES |
9 | Correct | 3 ms | 5020 KB | answer = NO |
10 | Correct | 2 ms | 4948 KB | answer = YES |
11 | Correct | 3 ms | 4948 KB | answer = YES |
12 | Correct | 3 ms | 5076 KB | answer = NO |
13 | Correct | 4 ms | 4948 KB | answer = YES |
14 | Correct | 3 ms | 4948 KB | answer = YES |
15 | Correct | 3 ms | 5012 KB | answer = YES |
16 | Correct | 3 ms | 5012 KB | answer = YES |
17 | Correct | 3 ms | 5016 KB | answer = YES |
18 | Correct | 2 ms | 4948 KB | answer = YES |
19 | Correct | 3 ms | 4948 KB | answer = YES |
20 | Correct | 3 ms | 4948 KB | answer = YES |
21 | Correct | 3 ms | 4948 KB | answer = YES |
22 | Correct | 3 ms | 4948 KB | answer = NO |
23 | Correct | 3 ms | 4948 KB | answer = NO |
24 | Correct | 3 ms | 5016 KB | answer = YES |
25 | Correct | 4 ms | 4948 KB | answer = YES |
26 | Correct | 3 ms | 4948 KB | answer = YES |
27 | Correct | 4 ms | 5016 KB | answer = YES |
28 | Correct | 3 ms | 4948 KB | answer = YES |
29 | Correct | 3 ms | 4948 KB | answer = YES |
30 | Correct | 3 ms | 5016 KB | answer = NO |
31 | Correct | 3 ms | 4948 KB | answer = YES |
32 | Correct | 3 ms | 5016 KB | answer = YES |
33 | Correct | 3 ms | 4948 KB | answer = YES |
34 | Correct | 3 ms | 4948 KB | answer = YES |
35 | Correct | 4 ms | 5016 KB | answer = YES |
36 | Correct | 3 ms | 4948 KB | answer = YES |
37 | Correct | 3 ms | 4948 KB | answer = YES |
38 | Correct | 3 ms | 4948 KB | answer = YES |
39 | Correct | 3 ms | 4948 KB | answer = YES |
40 | Correct | 3 ms | 5076 KB | answer = YES |
41 | Correct | 3 ms | 5076 KB | answer = NO |
42 | Correct | 3 ms | 5020 KB | answer = YES |
43 | Correct | 4 ms | 5080 KB | answer = YES |
44 | Correct | 4 ms | 5076 KB | answer = YES |
45 | Correct | 3 ms | 5016 KB | answer = YES |
46 | Correct | 3 ms | 4948 KB | answer = YES |
47 | Correct | 4 ms | 5004 KB | answer = YES |
48 | Correct | 4 ms | 5076 KB | answer = YES |
49 | Correct | 9 ms | 5844 KB | answer = YES |
50 | Correct | 10 ms | 6100 KB | answer = YES |
51 | Correct | 11 ms | 6180 KB | answer = YES |
52 | Correct | 7 ms | 5972 KB | answer = NO |
53 | Correct | 3 ms | 5076 KB | answer = YES |
54 | Correct | 5 ms | 5204 KB | answer = YES |
55 | Correct | 8 ms | 5460 KB | answer = YES |
56 | Correct | 12 ms | 5844 KB | answer = YES |
57 | Correct | 8 ms | 5668 KB | answer = YES |
58 | Correct | 8 ms | 5716 KB | answer = YES |
59 | Correct | 9 ms | 5668 KB | answer = YES |
60 | Correct | 11 ms | 5716 KB | answer = YES |
61 | Correct | 6 ms | 5324 KB | answer = YES |
62 | Correct | 68 ms | 12556 KB | answer = NO |
63 | Correct | 65 ms | 12604 KB | answer = YES |
64 | Correct | 61 ms | 12492 KB | answer = NO |
65 | Correct | 81 ms | 12612 KB | answer = YES |
66 | Correct | 4 ms | 5076 KB | answer = YES |
67 | Correct | 74 ms | 18840 KB | answer = YES |
68 | Correct | 82 ms | 18712 KB | answer = YES |
69 | Correct | 75 ms | 18636 KB | answer = YES |
70 | Correct | 96 ms | 23124 KB | answer = YES |
71 | Correct | 70 ms | 18716 KB | answer = YES |
72 | Correct | 72 ms | 13096 KB | answer = YES |
73 | Correct | 84 ms | 13096 KB | answer = YES |
74 | Correct | 53 ms | 13124 KB | answer = YES |
75 | Correct | 30 ms | 11984 KB | answer = NO |
76 | Correct | 12 ms | 6040 KB | answer = YES |
77 | Correct | 30 ms | 6996 KB | answer = YES |
78 | Correct | 38 ms | 8464 KB | answer = YES |
79 | Correct | 64 ms | 11936 KB | answer = YES |
80 | Correct | 62 ms | 13096 KB | answer = YES |
81 | Correct | 54 ms | 14100 KB | answer = NO |
82 | Correct | 81 ms | 18288 KB | answer = YES |
83 | Correct | 110 ms | 18796 KB | answer = YES |
84 | Correct | 101 ms | 18796 KB | answer = YES |
85 | Correct | 78 ms | 18776 KB | answer = YES |
86 | Correct | 70 ms | 18768 KB | answer = YES |
87 | Correct | 59 ms | 13068 KB | answer = NO |
88 | Correct | 116 ms | 14960 KB | answer = YES |
89 | Correct | 81 ms | 11836 KB | answer = YES |
90 | Correct | 77 ms | 11896 KB | answer = YES |
91 | Correct | 73 ms | 11928 KB | answer = YES |
92 | Correct | 36 ms | 9012 KB | answer = YES |
93 | Correct | 49 ms | 9032 KB | answer = YES |
94 | Correct | 82 ms | 17136 KB | answer = NO |
95 | Correct | 61 ms | 11140 KB | answer = NO |
96 | Correct | 144 ms | 20580 KB | answer = YES |
97 | Correct | 41 ms | 17128 KB | answer = NO |