Submission #557820

#	Time	Username	Problem	Language	Result	Execution time	Memory
557820		Ai7081	Graph (BOI20_graph)	C++17	100 / 100	142 ms	20264 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);
    while (m--) {
        int u, v, w;
        scanf(" %d %d %d", &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"); return 0;}
        if (!markx) {
            a.clear();
            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]);
    return 0;
}

Compilation message (stderr)

Graph.cpp: In function 'int main()':
Graph.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |     scanf(" %d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
Graph.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         scanf(" %d %d %d", &u, &v, &w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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