제출 #1280083

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280083		MisterReaper	Graph (BOI20_graph)	C++20	0 / 100	1 ms	436 KiB

Graph

// File graph.cpp created on 16.10.2025 at 21:27:38
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int max_N = int(1E5) + 5;
constexpr int max_M = int(2E5) + 5;
constexpr int inf = int(1E9);
constexpr double EPS = 1E-4;

int N, M;
int E[max_M][3];
std::vector<int> adj[max_N];

int vis[max_N];
int A[max_N][2];

double ans[max_N];

double dif = inf;
std::vector<int> vrt;

void dfs(int v) {
    vrt.emplace_back(v);
    vis[v] = true;
    for (auto i : adj[v]) {
        int u = E[i][0] ^ E[i][1] ^ v;
        int na = -A[v][0];
        int nb = E[i][2] - A[v][1];
        if (vis[u]) {
            if (A[u][0] == na) {
                if (nb == A[u][1]) {
                    // ok
                } else {
                    // bad
                    std::cout << "NO\n";
                    exit(0);
                }
            } else if (A[u][0] == -na) {
                int c = (nb - A[u][1]);
                debug(dif, 1.0 * c / (A[u][0] - na));
                if (std::abs(dif - inf) < EPS) {
                    dif = 1.0 * c / (A[u][0] - na);
                } else {
                    if (std::abs(dif - 1.0 * c / (A[u][0] - na)) > EPS) {
                        std::cout << "NO\n";
                        exit(0);
                    }
                }
            }
        } else {
            A[u][0] = na;
            A[u][1] = nb;
            dfs(u);
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cout << std::fixed << std::setprecision(9);

    std::cin >> N >> M;

    for (int i = 0; i < M; ++i) {
        std::cin >> E[i][0] >> E[i][1] >> E[i][2];
        --E[i][0], --E[i][1];
        adj[E[i][0]].emplace_back(i);
        adj[E[i][1]].emplace_back(i);
    }

    for (int v = 0; v < N; ++v) {
        if (vis[v]) {
            continue;
        }
        A[v][0] = 1;
        A[v][1] = 0;
        vrt.clear();
        dif = inf;
        dfs(v);
        double x;
        if (std::abs(dif - inf) > EPS) {
            x = dif;
        } else {
            std::vector<int> all;
            for (auto u : vrt) {
                all.emplace_back(A[u][1] * A[u][0]);
            }
            std::sort(all.begin(), all.end());
            x = all[int(vrt.size()) / 2];
        }
        for (auto u : vrt) {
            ans[u] = A[u][0] * x + A[u][1];
        }
    }

    std::cout << "YES\n";
    for (int i = 0; i < N; ++i) {
        std::cout << ans[i] << " \n"[i == N - 1];
    }

    return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 17
• Subtask 3: 0 / 24
• Subtask 4: 0 / 42
• Subtask 5: 0 / 5