oj.uz

Submission #882998

# Submission time Handle Problem Language Result Execution time Memory
882998 2023-12-04T11:35:18 Z vjudge1 Graph (BOI20_graph) C++17
100 / 100
 120 ms 20176 KB 
// https://oj.uz/problem/view/BOI20_graph

#include <bits/stdc++.h>
using namespace std;

namespace std {

template <class Fun>
class y_combinator_result {
        Fun fun_;

       public:
        template <class T>
        explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)) {}

        template <class... Args>
        decltype(auto) operator()(Args &&...args) {
                return fun_(std::ref(*this), std::forward<Args>(args)...);
        }
};

template <class Fun>
decltype(auto) y_combinator(Fun &&fun) {
        return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

/* Example
        auto fun = y_combinator([&](auto self, int x) -> void {
                self(x + 1);
        });
*/

}  // namespace std

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);

        int n, m;
        cin >> n >> m;
        vector<vector<pair<int, int>>> adj(n);
        for (int i = 0; i < m; i++) {
                int u, v, k;
                cin >> u >> v >> k;
                u--, v--;
                adj[u].emplace_back(v, k * 2);
                adj[v].emplace_back(u, k * 2);
        }

        vector<int> a(n);
        vector<int> done(n);
        vector<int> d(n);
        vector<int> ans(n);
        const int inf = 1e9;

        auto solve = [&](int source) {
                vector<int> node;
                int low = -inf, high = +inf;
                a[source] = d[source] = 0;
                auto dfs = y_combinator([&](auto self, int u) -> void {
                        done[u] = 1;
                        for (auto [v, k] : adj[u]) {
                                if (done[v] == 0) {
                                        d[v] = d[u] ^ 1;
                                        a[v] = k - a[u];
                                        self(v);
                                } else if (d[v] == d[u]) {
                                        int aa = k - a[u];
                                        int x = aa - a[v] >> 1;
                                        if (d[v]) x = -x;
                                        low = max(low, x);
                                        high = min(high, x);
                                } else {
                                        if (a[v] != k - a[u]) low = +inf, high = -inf;
                                }
                        }
                        node.emplace_back(u);
                });
                dfs(source);
                if (low > high) {
                        cout << "NO\n";
                        exit(0);
                }
                if (low == high) {
                        for (int i : node) {
                                ans[i] = (d[i] ? -1 : +1) * high + a[i];
                        }
                } else {
                        vector<pair<int, int>> events;
                        for (int i : node) {
                                if (d[i] == 0) {
                                        events.emplace_back(-a[i], +1);
                                } else {
                                        events.emplace_back(+a[i], -1);
                                }
                        }
                        sort(events.begin(), events.end());
                        assert(events[0].first >= -n * 2);
                        int64_t sum = 0;
                        vector<int> neg(2), pos(2);
                        for (int i : node) {
                                ans[i] = (d[i] ? -1 : +1) * (-n * 2) + a[i];
                                sum += abs(ans[i]);
                                auto &which = ans[i] >= 0 ? pos : neg;
                                which[d[i]]++;
                        }
                        int last = -n * 2;
                        int64_t best = sum, x = -n * 2;
                        for (int i = 0, j = 0; i < events.size(); i = j) {
                                while (j < events.size() && events[j].first == events[i].first) j++;
                                int dist = events[i].first - last;
                                sum += 1ll * (neg[1] + pos[0]) * dist;
                                sum -= 1ll * (neg[0] + pos[1]) * dist;
                                if (best > sum) best = sum, x = events[i].first;
                                for (int k = i; k < j; k++) {
                                        if (events[k].second == +1) {
                                                neg[0]--;
                                                pos[0]++;
                                        } else {
                                                pos[1]--;
                                                neg[1]++;
                                        }
                                }
                                last = events[i].first;
                        }
                        for (int i : node) {
                                ans[i] = (d[i] ? -1 : +1) * x + a[i];
                        }
                }
        };

        for (int i = 0; i < n; i++) {
                if (done[i]) continue;
                solve(i);
        }

        cout << "YES\n";
        for (int i = 0; i < n; i++) {
                if (ans[i] < 0) cout << '-';
                cout << abs(ans[i]) / 2;
                if (ans[i] % 2) cout << ".5";
                cout << ' ';
        }
}

Compilation message

Graph.cpp: In lambda function:
Graph.cpp:109:50: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |                         for (int i = 0, j = 0; i < events.size(); i = j) {
      |                                                ~~^~~~~~~~~~~~~~~
Graph.cpp:110:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |                                 while (j < events.size() && events[j].first == events[i].first) j++;
      |                                        ~~^~~~~~~~~~~~~~~
Graph.cpp: In instantiation of 'main()::<lambda(int)>::<lambda(auto:23, int)> [with auto:23 = std::reference_wrapper<std::y_combinator_result<main()::<lambda(int)>::<lambda(auto:23, int)> > >]':
Graph.cpp:18:28:   required from 'decltype(auto) std::y_combinator_result<Fun>::operator()(Args&& ...) [with Args = {int&}; Fun = main()::<lambda(int)>::<lambda(auto:23, int)>]'
Graph.cpp:79:27:   required from here
Graph.cpp:69:52: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   69 |                                         int x = aa - a[v] >> 1;
      |                                                 ~~~^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
17.0 / 17.0

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

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB answer = YES
2 Correct 0 ms 348 KB answer = YES
3 Correct 0 ms 348 KB answer = YES
4 Correct 0 ms 348 KB answer = NO
5 Correct 0 ms 348 KB answer = YES
6 Correct 0 ms 348 KB answer = YES
7 Correct 0 ms 348 KB answer = YES
8 Correct 1 ms 344 KB answer = YES
9 Correct 0 ms 348 KB answer = NO
10 Correct 0 ms 348 KB answer = YES
11 Correct 0 ms 348 KB answer = YES
12 Correct 1 ms 348 KB answer = NO
13 Correct 0 ms 348 KB answer = YES
14 Correct 1 ms 348 KB answer = YES
15 Correct 0 ms 348 KB answer = YES
16 Correct 0 ms 348 KB answer = YES
17 Correct 0 ms 348 KB answer = YES
18 Correct 1 ms 348 KB answer = YES
19 Correct 1 ms 452 KB answer = YES
20 Correct 0 ms 344 KB answer = YES
21 Correct 0 ms 348 KB answer = YES
22 Correct 0 ms 348 KB answer = NO
23 Correct 0 ms 348 KB answer = NO
24 Correct 0 ms 344 KB answer = YES
25 Correct 0 ms 344 KB answer = YES
26 Correct 1 ms 344 KB answer = YES
27 Correct 0 ms 348 KB answer = YES
28 Correct 0 ms 348 KB answer = YES
29 Correct 1 ms 344 KB answer = YES
30 Correct 0 ms 344 KB answer = NO
31 Correct 0 ms 424 KB answer = YES
32 Correct 0 ms 344 KB answer = YES
33 Correct 0 ms 348 KB answer = YES
34 Correct 0 ms 348 KB answer = YES
35 Correct 0 ms 348 KB answer = YES
36 Correct 0 ms 348 KB answer = YES
37 Correct 1 ms 348 KB answer = YES
38 Correct 0 ms 460 KB answer = YES
39 Correct 1 ms 348 KB answer = YES
40 Correct 1 ms 516 KB answer = YES
41 Correct 1 ms 348 KB answer = NO
42 Correct 1 ms 348 KB answer = YES
43 Correct 1 ms 348 KB answer = YES
44 Correct 1 ms 348 KB answer = YES
45 Correct 1 ms 348 KB answer = YES
46 Correct 0 ms 348 KB answer = YES
47 Correct 1 ms 460 KB answer = YES
48 Correct 1 ms 348 KB answer = YES
49 Correct 4 ms 1372 KB answer = YES
50 Correct 4 ms 1744 KB answer = YES
51 Correct 4 ms 1748 KB answer = YES
52 Correct 3 ms 1624 KB answer = NO
53 Correct 1 ms 348 KB answer = YES
54 Correct 1 ms 604 KB answer = YES
55 Correct 4 ms 860 KB answer = YES
56 Correct 4 ms 1368 KB answer = YES
57 Correct 4 ms 1372 KB answer = YES
58 Correct 4 ms 1372 KB answer = YES
59 Correct 3 ms 1116 KB answer = YES
60 Correct 5 ms 1372 KB answer = YES
61 Correct 2 ms 856 KB answer = YES
62 Correct 43 ms 8020 KB answer = NO
63 Correct 60 ms 8140 KB answer = YES
64 Correct 40 ms 8204 KB answer = NO
65 Correct 47 ms 8020 KB answer = YES
66 Correct 1 ms 600 KB answer = YES

Subtask #5
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB answer = YES
2 Correct 0 ms 348 KB answer = YES
3 Correct 0 ms 348 KB answer = YES
4 Correct 0 ms 348 KB answer = NO
5 Correct 0 ms 348 KB answer = YES
6 Correct 0 ms 348 KB answer = YES
7 Correct 0 ms 348 KB answer = YES
8 Correct 1 ms 344 KB answer = YES
9 Correct 0 ms 348 KB answer = NO
10 Correct 0 ms 348 KB answer = YES
11 Correct 0 ms 348 KB answer = YES
12 Correct 1 ms 348 KB answer = NO
13 Correct 0 ms 348 KB answer = YES
14 Correct 1 ms 348 KB answer = YES
15 Correct 0 ms 348 KB answer = YES
16 Correct 0 ms 348 KB answer = YES
17 Correct 0 ms 348 KB answer = YES
18 Correct 1 ms 348 KB answer = YES
19 Correct 1 ms 452 KB answer = YES
20 Correct 0 ms 344 KB answer = YES
21 Correct 0 ms 348 KB answer = YES
22 Correct 0 ms 348 KB answer = NO
23 Correct 0 ms 348 KB answer = NO
24 Correct 0 ms 344 KB answer = YES
25 Correct 0 ms 344 KB answer = YES
26 Correct 1 ms 344 KB answer = YES
27 Correct 0 ms 348 KB answer = YES
28 Correct 0 ms 348 KB answer = YES
29 Correct 1 ms 344 KB answer = YES
30 Correct 0 ms 344 KB answer = NO
31 Correct 0 ms 424 KB answer = YES
32 Correct 0 ms 344 KB answer = YES
33 Correct 0 ms 348 KB answer = YES
34 Correct 0 ms 348 KB answer = YES
35 Correct 0 ms 348 KB answer = YES
36 Correct 0 ms 348 KB answer = YES
37 Correct 1 ms 348 KB answer = YES
38 Correct 0 ms 460 KB answer = YES
39 Correct 1 ms 348 KB answer = YES
40 Correct 1 ms 516 KB answer = YES
41 Correct 1 ms 348 KB answer = NO
42 Correct 1 ms 348 KB answer = YES
43 Correct 1 ms 348 KB answer = YES
44 Correct 1 ms 348 KB answer = YES
45 Correct 1 ms 348 KB answer = YES
46 Correct 0 ms 348 KB answer = YES
47 Correct 1 ms 460 KB answer = YES
48 Correct 1 ms 348 KB answer = YES
49 Correct 4 ms 1372 KB answer = YES
50 Correct 4 ms 1744 KB answer = YES
51 Correct 4 ms 1748 KB answer = YES
52 Correct 3 ms 1624 KB answer = NO
53 Correct 1 ms 348 KB answer = YES
54 Correct 1 ms 604 KB answer = YES
55 Correct 4 ms 860 KB answer = YES
56 Correct 4 ms 1368 KB answer = YES
57 Correct 4 ms 1372 KB answer = YES
58 Correct 4 ms 1372 KB answer = YES
59 Correct 3 ms 1116 KB answer = YES
60 Correct 5 ms 1372 KB answer = YES
61 Correct 2 ms 856 KB answer = YES
62 Correct 43 ms 8020 KB answer = NO
63 Correct 60 ms 8140 KB answer = YES
64 Correct 40 ms 8204 KB answer = NO
65 Correct 47 ms 8020 KB answer = YES
66 Correct 1 ms 600 KB answer = YES
67 Correct 45 ms 16464 KB answer = YES
68 Correct 46 ms 16464 KB answer = YES
69 Correct 35 ms 15840 KB answer = YES
70 Correct 61 ms 20176 KB answer = YES
71 Correct 43 ms 15608 KB answer = YES
72 Correct 45 ms 10916 KB answer = YES
73 Correct 39 ms 10016 KB answer = YES
74 Correct 33 ms 9424 KB answer = YES
75 Correct 19 ms 9432 KB answer = NO
76 Correct 5 ms 1624 KB answer = YES
77 Correct 10 ms 3032 KB answer = YES
78 Correct 17 ms 4952 KB answer = YES
79 Correct 37 ms 9556 KB answer = YES
80 Correct 28 ms 9852 KB answer = YES
81 Correct 28 ms 12752 KB answer = NO
82 Correct 40 ms 15172 KB answer = YES
83 Correct 44 ms 15564 KB answer = YES
84 Correct 59 ms 16644 KB answer = YES
85 Correct 41 ms 16460 KB answer = YES
86 Correct 35 ms 15564 KB answer = YES
87 Correct 39 ms 10752 KB answer = NO
88 Correct 48 ms 11948 KB answer = YES
89 Correct 36 ms 9040 KB answer = YES
90 Correct 40 ms 9040 KB answer = YES
91 Correct 45 ms 9044 KB answer = YES
92 Correct 18 ms 5180 KB answer = YES
93 Correct 21 ms 5208 KB answer = YES
94 Correct 45 ms 15724 KB answer = NO
95 Correct 26 ms 8796 KB answer = NO
96 Correct 120 ms 17644 KB answer = YES
97 Correct 29 ms 15652 KB answer = NO