Submission #395346

#	Time	Username	Problem	Language	Result	Execution time	Memory
395346		KoD	Graph (BOI20_graph)	C++17	100 / 100	324 ms	20080 KiB

Graph

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