Submission #557812

#	Time	Username	Problem	Language	Result	Execution time	Memory
557812		Ai7081	Graph (BOI20_graph)	C++17	5 / 100	2 ms	2656 KiB

Graph

#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second

const int N = 1e5 + 5;

int n, m;
double ans[N];
pair<int, int> val[N], x;
bool mark[N], markx, fail;
vector<pair<int, int>> adj[N];
vector<int> a, now;

void dfs(int v) {
    if (fail) return;
    mark[v] = true;
    now.push_back(v);
    for (auto [to, w] : adj[v]) {
        if (mark[to]) {
            if (val[v].nd != val[to].nd) {
                if (val[v].st + val[to].st != w) {fail = true; return;}
            }
            else {
                if (markx) {
                    if (x.nd*(val[v].st+val[to].st) + x.st*(val[v].nd+val[to].nd) != x.nd*w) {
                        fail = true; return;
                    }
                }
                else if (val[v].nd == val[to].nd) {
                    x = {w-(val[v].st+val[to].st), val[v].nd+val[to].nd};
                    markx = true;
                }
            }
        }
        else {
            val[to] = {w-val[v].st, -val[v].nd};
            dfs(to);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
//    scanf(" %d %d", &n, &m);
    cin >> n >> m;
    while (m--) {
        int u, v, w;
//        scanf(" %d %d %d", &u, &v, &w);
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    for (int i=1; i<=n; i++) if (!mark[i]) {
        markx = false;
        now.clear();
        val[i] = {0, 1};
        dfs(i);
        if (fail) {/*printf("NO");*/ cout << "NO"; return 0;}
        if (!markx) {
            for (auto i : now) a.push_back(-val[i].nd*val[i].st);
            sort(a.begin(), a.end());
            x = {a[a.size()/2], 1};
        }
        for (auto i : now) ans[i] = (double)(x.st*val[i].nd+x.nd*val[i].st) / (double)x.nd;
    }
//    printf("YES\n");
//    for (int i=1; i<=n; i++) printf("%lf ", ans[i]);
    cout << "YES\n";
    for (int i=1; i<=n; i++) cout << ans[i] << ' ';
    return 0;
}

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