Submission #308743

#	Time	Username	Problem	Language	Result	Execution time	Memory
308743		VEGAnn	Graph (BOI20_graph)	C++14	100 / 100	191 ms	20976 KiB

Graph

#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define PB push_back
#define sz(x) ((int)x.size())
#define i2 array<int,2>
using namespace std;
typedef long double ld;
const int oo = 2e9;
const int N = 100100;
const int M = 200100;
vector<i2> g[N];
vector<int> vc;
int n, m, a[N], b[N], ans[N], glob_mem;
bool was[N], cenok;

void BAD(){
    cout << "NO";
    exit(0);
}

void go(int v, int vl){
    if (was[v]){
        if (ans[v] != vl)
            BAD();
        return;
    }

    was[v] = 1;
    ans[v] = vl;

    for (i2 u : g[v])
        go(u[0], u[1] - vl);
}

void dfs(int v, int na, int nb){
    if (cenok) return;

    if (a[v] != 0){
        if (na == a[v]){
            if (nb != b[v])
                BAD();
        } else {
            cenok = 1;

            int vl = 0;

            if (na == 1)
                vl = b[v] - nb;
            else vl = nb - b[v];

            vl >>= 1;

            glob_mem = vl;
        }

        return;
    }

    if (na == 1)
        vc.PB(-nb);
    else vc.PB(nb);

    a[v] = na;
    b[v] = nb;

    for (i2 u : g[v]){
        if (cenok) return;

        dfs(u[0], -na, u[1] - nb);
    }
}

void last_dfs(int v, int x){
    if (was[v]) return;

    was[v] = 1;

    ans[v] = a[v] * x + b[v];

    for (i2 u : g[v])
        last_dfs(u[0], x);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> m;

    for (int i = 0; i < m; i++){
        int x, y, z; cin >> x >> y >> z;
        z += z; x--; y--;

        g[x].PB({y, z});
        g[y].PB({x, z});
    }

    fill(ans, ans + n, oo);

    for (int i = 0; i < n; i++){
        if (was[i]) continue;

        vc.clear();

        cenok = 0;

        dfs(i, 1, 0);

        if (cenok) {
            go(i, glob_mem);
            continue;
        }

        sort(all(vc));

        last_dfs(i, vc[sz(vc) / 2]);
    }

    cout << "YES\n";

    for (int i = 0; i < n; i++)
        cout << fixed << setprecision(10) << ld(ans[i]) / 2.0 << " ";

    return 0;
}

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