oj.uz

Submission #395345

# Submission time Handle Problem Language Result Execution time Memory
395345 2021-04-28T08:48:09 Z KoD Graph (BOI20_graph) C++17
100 / 100
 330 ms 22532 KB 
#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

int main() {
    int N, M;
    std::cin >> N >> M;
    Vec<int> A(M), B(M), C(M);
    Vec<Vec<std::pair<int, int>>> graph(N);
    for (int i = 0; i < M; ++i) {
        std::cin >> A[i] >> B[i] >> C[i];
        A[i] -= 1;
        B[i] -= 1;
        C[i] *= 2;
        graph[A[i]].emplace_back(B[i], C[i]);
        graph[B[i]].emplace_back(A[i], C[i]);
    }
    Vec<bool> done(N);
    Vec<std::pair<int, int>> coeff(N);
    Vec<int> val(N);
    Vec<int> visited;
    auto dfs = [&](auto&& dfs, const int u) -> void {
        done[u] = true;
        visited.push_back(u);
        for (const auto [v, c]: graph[u]) {
            if (!done[v]) {
                coeff[v].first = -coeff[u].first;
                coeff[v].second = c - coeff[u].second;
                dfs(dfs, v);
            }
        }
    };
    for (int src = 0; src < N; ++src) {
        if (!done[src]) {
            coeff[src].first = 1;
            coeff[src].second = 0;
            dfs(dfs, src);
            bool sole = false;
            Vec<int> pts;
            for (const auto u: visited) {
                pts.push_back(-coeff[u].first * coeff[u].second);
                for (const auto [v, c]: graph[u]) {
                    if (coeff[u].first == coeff[v].first) {
                        val[src] = (c - coeff[u].second - coeff[v].second) / (coeff[u].first + coeff[v].first);
                        sole = true;
                    }
                }
            }
            if (!sole) {
                std::sort(pts.begin(), pts.end());
                val[src] = pts[pts.size() / 2];
            }
            for (const auto u: visited) {
                if (u != src) {
                    val[u] = val[src] * coeff[u].first + coeff[u].second;
                }
            }
            visited.clear();
        }
    }
    for (int i = 0; i < M; ++i) {
        if (val[A[i]] + val[B[i]] != C[i]) {
            std::cout << "NO\n";
            return 0;
        }
    }
    std::cout << "YES\n";
    for (int i = 0; i < N; ++i) {
        std::cout << (double) val[i] / 2 << " \n"[i + 1 == N];
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB answer = YES
2 Correct 1 ms 204 KB answer = YES
3 Correct 1 ms 204 KB answer = YES
4 Correct 1 ms 296 KB answer = NO
5 Correct 1 ms 268 KB answer = YES
6 Correct 1 ms 204 KB answer = YES
7 Correct 1 ms 204 KB answer = YES
8 Correct 1 ms 204 KB answer = YES
9 Correct 1 ms 208 KB answer = NO
10 Correct 1 ms 204 KB answer = YES
11 Correct 1 ms 204 KB answer = YES
12 Correct 1 ms 204 KB answer = NO
13 Correct 1 ms 204 KB answer = YES
14 Correct 1 ms 204 KB answer = YES
15 Correct 1 ms 204 KB answer = YES
16 Correct 1 ms 204 KB answer = YES
17 Correct 1 ms 204 KB answer = YES
18 Correct 1 ms 204 KB answer = YES
19 Correct 1 ms 204 KB answer = YES
20 Correct 1 ms 292 KB answer = YES
21 Correct 1 ms 204 KB answer = YES
22 Correct 1 ms 204 KB answer = NO
23 Correct 1 ms 204 KB answer = NO

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB answer = YES
2 Correct 1 ms 204 KB answer = YES
3 Correct 1 ms 204 KB answer = YES
4 Correct 1 ms 296 KB answer = NO
5 Correct 1 ms 268 KB answer = YES
6 Correct 1 ms 204 KB answer = YES
7 Correct 1 ms 204 KB answer = YES
8 Correct 1 ms 204 KB answer = YES
9 Correct 1 ms 208 KB answer = NO
10 Correct 1 ms 204 KB answer = YES
11 Correct 1 ms 204 KB answer = YES
12 Correct 1 ms 204 KB answer = NO
13 Correct 1 ms 204 KB answer = YES
14 Correct 1 ms 204 KB answer = YES
15 Correct 1 ms 204 KB answer = YES
16 Correct 1 ms 204 KB answer = YES
17 Correct 1 ms 204 KB answer = YES
18 Correct 1 ms 204 KB answer = YES
19 Correct 1 ms 204 KB answer = YES
20 Correct 1 ms 292 KB answer = YES
21 Correct 1 ms 204 KB answer = YES
22 Correct 1 ms 204 KB answer = NO
23 Correct 1 ms 204 KB answer = NO
24 Correct 1 ms 204 KB answer = YES
25 Correct 1 ms 204 KB answer = YES
26 Correct 1 ms 204 KB answer = YES
27 Correct 1 ms 204 KB answer = YES
28 Correct 1 ms 204 KB answer = YES
29 Correct 1 ms 204 KB answer = YES
30 Correct 1 ms 204 KB answer = NO
31 Correct 1 ms 204 KB answer = YES
32 Correct 1 ms 204 KB answer = YES
33 Correct 1 ms 204 KB answer = YES
34 Correct 1 ms 204 KB answer = YES
35 Correct 1 ms 208 KB answer = YES
36 Correct 1 ms 204 KB answer = YES

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB answer = YES
2 Correct 1 ms 204 KB answer = YES
3 Correct 1 ms 204 KB answer = YES
4 Correct 1 ms 296 KB answer = NO
5 Correct 1 ms 268 KB answer = YES
6 Correct 1 ms 204 KB answer = YES
7 Correct 1 ms 204 KB answer = YES
8 Correct 1 ms 204 KB answer = YES
9 Correct 1 ms 208 KB answer = NO
10 Correct 1 ms 204 KB answer = YES
11 Correct 1 ms 204 KB answer = YES
12 Correct 1 ms 204 KB answer = NO
13 Correct 1 ms 204 KB answer = YES
14 Correct 1 ms 204 KB answer = YES
15 Correct 1 ms 204 KB answer = YES
16 Correct 1 ms 204 KB answer = YES
17 Correct 1 ms 204 KB answer = YES
18 Correct 1 ms 204 KB answer = YES
19 Correct 1 ms 204 KB answer = YES
20 Correct 1 ms 292 KB answer = YES
21 Correct 1 ms 204 KB answer = YES
22 Correct 1 ms 204 KB answer = NO
23 Correct 1 ms 204 KB answer = NO
24 Correct 1 ms 204 KB answer = YES
25 Correct 1 ms 204 KB answer = YES
26 Correct 1 ms 204 KB answer = YES
27 Correct 1 ms 204 KB answer = YES
28 Correct 1 ms 204 KB answer = YES
29 Correct 1 ms 204 KB answer = YES
30 Correct 1 ms 204 KB answer = NO
31 Correct 1 ms 204 KB answer = YES
32 Correct 1 ms 204 KB answer = YES
33 Correct 1 ms 204 KB answer = YES
34 Correct 1 ms 204 KB answer = YES
35 Correct 1 ms 208 KB answer = YES
36 Correct 1 ms 204 KB answer = YES
37 Correct 1 ms 204 KB answer = YES
38 Correct 1 ms 204 KB answer = YES
39 Correct 1 ms 332 KB answer = YES
40 Correct 2 ms 332 KB answer = YES
41 Correct 1 ms 332 KB answer = NO
42 Correct 2 ms 336 KB answer = YES
43 Correct 2 ms 332 KB answer = YES
44 Correct 2 ms 332 KB answer = YES
45 Correct 2 ms 332 KB answer = YES
46 Correct 1 ms 332 KB answer = YES
47 Correct 2 ms 332 KB answer = YES
48 Correct 2 ms 332 KB answer = YES

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB answer = YES
2 Correct 1 ms 204 KB answer = YES
3 Correct 1 ms 204 KB answer = YES
4 Correct 1 ms 296 KB answer = NO
5 Correct 1 ms 268 KB answer = YES
6 Correct 1 ms 204 KB answer = YES
7 Correct 1 ms 204 KB answer = YES
8 Correct 1 ms 204 KB answer = YES
9 Correct 1 ms 208 KB answer = NO
10 Correct 1 ms 204 KB answer = YES
11 Correct 1 ms 204 KB answer = YES
12 Correct 1 ms 204 KB answer = NO
13 Correct 1 ms 204 KB answer = YES
14 Correct 1 ms 204 KB answer = YES
15 Correct 1 ms 204 KB answer = YES
16 Correct 1 ms 204 KB answer = YES
17 Correct 1 ms 204 KB answer = YES
18 Correct 1 ms 204 KB answer = YES
19 Correct 1 ms 204 KB answer = YES
20 Correct 1 ms 292 KB answer = YES
21 Correct 1 ms 204 KB answer = YES
22 Correct 1 ms 204 KB answer = NO
23 Correct 1 ms 204 KB answer = NO
24 Correct 1 ms 204 KB answer = YES
25 Correct 1 ms 204 KB answer = YES
26 Correct 1 ms 204 KB answer = YES
27 Correct 1 ms 204 KB answer = YES
28 Correct 1 ms 204 KB answer = YES
29 Correct 1 ms 204 KB answer = YES
30 Correct 1 ms 204 KB answer = NO
31 Correct 1 ms 204 KB answer = YES
32 Correct 1 ms 204 KB answer = YES
33 Correct 1 ms 204 KB answer = YES
34 Correct 1 ms 204 KB answer = YES
35 Correct 1 ms 208 KB answer = YES
36 Correct 1 ms 204 KB answer = YES
37 Correct 1 ms 204 KB answer = YES
38 Correct 1 ms 204 KB answer = YES
39 Correct 1 ms 332 KB answer = YES
40 Correct 2 ms 332 KB answer = YES
41 Correct 1 ms 332 KB answer = NO
42 Correct 2 ms 336 KB answer = YES
43 Correct 2 ms 332 KB answer = YES
44 Correct 2 ms 332 KB answer = YES
45 Correct 2 ms 332 KB answer = YES
46 Correct 1 ms 332 KB answer = YES
47 Correct 2 ms 332 KB answer = YES
48 Correct 2 ms 332 KB answer = YES
49 Correct 16 ms 1312 KB answer = YES
50 Correct 15 ms 1708 KB answer = YES
51 Correct 15 ms 1612 KB answer = YES
52 Correct 10 ms 1592 KB answer = NO
53 Correct 2 ms 336 KB answer = YES
54 Correct 4 ms 584 KB answer = YES
55 Correct 8 ms 844 KB answer = YES
56 Correct 14 ms 1328 KB answer = YES
57 Correct 14 ms 1228 KB answer = YES
58 Correct 13 ms 1228 KB answer = YES
59 Correct 14 ms 1264 KB answer = YES
60 Correct 15 ms 1356 KB answer = YES
61 Correct 8 ms 844 KB answer = YES
62 Correct 168 ms 10436 KB answer = NO
63 Correct 196 ms 10368 KB answer = YES
64 Correct 171 ms 10372 KB answer = NO
65 Correct 175 ms 10416 KB answer = YES
66 Correct 4 ms 460 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB answer = YES
2 Correct 1 ms 204 KB answer = YES
3 Correct 1 ms 204 KB answer = YES
4 Correct 1 ms 296 KB answer = NO
5 Correct 1 ms 268 KB answer = YES
6 Correct 1 ms 204 KB answer = YES
7 Correct 1 ms 204 KB answer = YES
8 Correct 1 ms 204 KB answer = YES
9 Correct 1 ms 208 KB answer = NO
10 Correct 1 ms 204 KB answer = YES
11 Correct 1 ms 204 KB answer = YES
12 Correct 1 ms 204 KB answer = NO
13 Correct 1 ms 204 KB answer = YES
14 Correct 1 ms 204 KB answer = YES
15 Correct 1 ms 204 KB answer = YES
16 Correct 1 ms 204 KB answer = YES
17 Correct 1 ms 204 KB answer = YES
18 Correct 1 ms 204 KB answer = YES
19 Correct 1 ms 204 KB answer = YES
20 Correct 1 ms 292 KB answer = YES
21 Correct 1 ms 204 KB answer = YES
22 Correct 1 ms 204 KB answer = NO
23 Correct 1 ms 204 KB answer = NO
24 Correct 1 ms 204 KB answer = YES
25 Correct 1 ms 204 KB answer = YES
26 Correct 1 ms 204 KB answer = YES
27 Correct 1 ms 204 KB answer = YES
28 Correct 1 ms 204 KB answer = YES
29 Correct 1 ms 204 KB answer = YES
30 Correct 1 ms 204 KB answer = NO
31 Correct 1 ms 204 KB answer = YES
32 Correct 1 ms 204 KB answer = YES
33 Correct 1 ms 204 KB answer = YES
34 Correct 1 ms 204 KB answer = YES
35 Correct 1 ms 208 KB answer = YES
36 Correct 1 ms 204 KB answer = YES
37 Correct 1 ms 204 KB answer = YES
38 Correct 1 ms 204 KB answer = YES
39 Correct 1 ms 332 KB answer = YES
40 Correct 2 ms 332 KB answer = YES
41 Correct 1 ms 332 KB answer = NO
42 Correct 2 ms 336 KB answer = YES
43 Correct 2 ms 332 KB answer = YES
44 Correct 2 ms 332 KB answer = YES
45 Correct 2 ms 332 KB answer = YES
46 Correct 1 ms 332 KB answer = YES
47 Correct 2 ms 332 KB answer = YES
48 Correct 2 ms 332 KB answer = YES
49 Correct 16 ms 1312 KB answer = YES
50 Correct 15 ms 1708 KB answer = YES
51 Correct 15 ms 1612 KB answer = YES
52 Correct 10 ms 1592 KB answer = NO
53 Correct 2 ms 336 KB answer = YES
54 Correct 4 ms 584 KB answer = YES
55 Correct 8 ms 844 KB answer = YES
56 Correct 14 ms 1328 KB answer = YES
57 Correct 14 ms 1228 KB answer = YES
58 Correct 13 ms 1228 KB answer = YES
59 Correct 14 ms 1264 KB answer = YES
60 Correct 15 ms 1356 KB answer = YES
61 Correct 8 ms 844 KB answer = YES
62 Correct 168 ms 10436 KB answer = NO
63 Correct 196 ms 10368 KB answer = YES
64 Correct 171 ms 10372 KB answer = NO
65 Correct 175 ms 10416 KB answer = YES
66 Correct 4 ms 460 KB answer = YES
67 Correct 150 ms 16804 KB answer = YES
68 Correct 141 ms 16836 KB answer = YES
69 Correct 161 ms 16928 KB answer = YES
70 Correct 238 ms 22532 KB answer = YES
71 Correct 189 ms 16832 KB answer = YES
72 Correct 165 ms 11176 KB answer = YES
73 Correct 165 ms 11140 KB answer = YES
74 Correct 128 ms 10088 KB answer = YES
75 Correct 88 ms 10056 KB answer = NO
76 Correct 18 ms 1612 KB answer = YES
77 Correct 37 ms 2984 KB answer = YES
78 Correct 71 ms 4996 KB answer = YES
79 Correct 159 ms 9740 KB answer = YES
80 Correct 108 ms 10044 KB answer = YES
81 Correct 121 ms 13836 KB answer = NO
82 Correct 191 ms 16248 KB answer = YES
83 Correct 196 ms 16884 KB answer = YES
84 Correct 205 ms 16836 KB answer = YES
85 Correct 156 ms 16820 KB answer = YES
86 Correct 160 ms 16812 KB answer = YES
87 Correct 158 ms 12020 KB answer = NO
88 Correct 212 ms 12776 KB answer = YES
89 Correct 177 ms 9664 KB answer = YES
90 Correct 176 ms 9760 KB answer = YES
91 Correct 170 ms 9692 KB answer = YES
92 Correct 85 ms 5724 KB answer = YES
93 Correct 87 ms 5708 KB answer = YES
94 Correct 132 ms 16848 KB answer = NO
95 Correct 136 ms 9408 KB answer = NO
96 Correct 330 ms 19932 KB answer = YES
97 Correct 108 ms 16784 KB answer = NO