Submission #336421

#	Time	Username	Problem	Language	Result	Execution time	Memory
336421		Joshc	Graph (BOI20_graph)	C++11	100 / 100	200 ms	23736 KiB

Graph

#include <cstdio>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;

#define f first
#define s second

vector<pair<int, int> > edges[100001];
vector<int> comp, xs;
double must;
pair<int, int> val[100001];
double ans[100001];

void quit() {
    printf("NO\n");
    exit(0);
}

void dfs(int v, int a, int b) {
    if (val[v].f == 0) val[v] = {a, b};
    else if (val[v].f != a || val[v].s != b) {
        if (val[v].f == a) quit();
        else {
            double cur = 1.0*(val[v].s-b)/(a-val[v].f);
            if (abs(must-1000000000000000000)>0.0000000001 && abs(must-cur)>0.0000000001) quit();
            must = cur;
        }
        return;
    } else return;
    comp.push_back(v);
    xs.push_back(a*b);
    for (auto u : edges[v]) dfs(u.f, -a, u.s-b);
}

void calc() {
    if (abs(must-1000000000000000000)>0.0000000001) {
        for (int i : comp) ans[i] = val[i].f*must+val[i].s;
        return;
    }
    nth_element(xs.begin(), xs.begin()+xs.size()/2, xs.end());
    int z = -xs[xs.size()/2];
    for (int i : comp) ans[i] = val[i].f*z+val[i].s;
}

int main() {
    int n, m, x, y, z;
    scanf("%d%d", &n, &m);
    while (m--) {
        scanf("%d%d%d", &x, &y, &z);
        edges[x].emplace_back(y, z);
        edges[y].emplace_back(x, z);
    }
    for (int i=1; i<=n; i++) val[i] = {0, 0};
    for (int i=1; i<=n; i++) {
        if (val[i].f == 0) {
            must = 1000000000000000000;
            comp.clear();
            xs.clear();
            dfs(i, 1, 0);
            calc();
        }
    }
    printf("YES\n");
    for (int i=1; i<=n; i++) printf("%.14lf ", ans[i]);
    printf("\n");
}

Compilation message (stderr)

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

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