제출 #882998

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
882998		vjudge1	Graph (BOI20_graph)	C++17	100 / 100	120 ms	20176 KiB

Graph

// 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 << ' ';
        }
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 5
• Subtask 2: 12 / 12
• Subtask 3: 17 / 17
• Subtask 4: 24 / 24
• Subtask 5: 42 / 42