Submission #1260539

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260539		anteknne	Graph (BOI20_graph)	C++20	0 / 100	1 ms	2628 KiB

Graph

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

const int MAXN = 100 * 1000 + 17;
const int INF = 100 * 1000 * 1000;
vector<pii> graf[MAXN];
bool odw[MAXN];
pii w[MAXN];
int n;
ld c[MAXN];
bool ok;
map<pii, int> mapa;
vector<int> vec;
ld wx = -10000;
vector<int> akt;
vector<int> piwoni;

void DFS (int v, int o) {
    akt.pb(v);
    for (auto x : graf[v]) {
        if (!odw[x.st]) {
            odw[x.st] = true;
            w[x.st].st = -1 * w[v].st;
            w[x.st].nd = x.nd - w[v].nd;
            DFS(x.st, v);
        } else if (x.st != o) {
            if (w[x.st].st != w[v].st && w[x.st].nd + w[v].nd != x.nd) {
                ok = false;
            }
            if (w[x.st].st == w[v].st) {
                wx = ld(x.nd - w[v].nd - w[x.st].nd)/ ld(2 * w[x.st].st);
                //cout << v << " " << x.st << ": " << wx << "\n";
            }
        }
    }
}

void DFS2 (int v) {
    for (auto x : graf[v]) {
        if (!odw[x.st]) {
            odw[x.st] = true;
            c[x.st] = ld(x.nd) - c[v];
            DFS2(x.st);
        } else {
            if (c[x.st] + c[v] != ld(x.nd)) {
                ok = false;
            }
        }
    }
}

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

    int m;
    cin >> n >> m;

    int a, b, r;

    bool kon = false;
    for (int i = 0; i < m; i ++) {
        cin >> a >> b >> r;
        if (mapa[{a, b}] > 0 && mapa[{a, b}] != r) {
            kon = true;
        }
        if (mapa[{a, b}] == 0) {
            if (a == b) {
                c[a] = ld(r)/ld(2);
                vec.pb(a);
            }
            graf[a].pb({b, r});
            graf[b].pb({a, r});
            mapa[{a, b}] = r;
            mapa[{b, a}] = r;
        }
    }

    if (kon) {
        cout << "NO\n";
        return 0;
    }

    ok = true;
    for (auto x : vec) {
        if (!odw[x]) {
            odw[x] = true;
            DFS2(x);
        }
    }

    //cout << int(vec.size()) << "\n";
    for (int i = 1; i <= n; i ++) {
        if (odw[i]) {
            continue;
        }
        odw[i] = true;
        w[i] = {1, 0};
        akt.clear();
        piwoni.clear();
        DFS(i, i);
        if (wx != -10000) {
            c[i] = wx;
            //cout << fixed << setprecision(5) << wx << "\n";
            for (auto x : akt) {
                odw[x] = false;
            }
            odw[i] = true;
            DFS2(i);
        } else {
            for (auto x : akt) {
                piwoni.pb(w[x].st * w[x].nd);
            }
            sort(piwoni.begin(), piwoni.end());
            wx = piwoni[int(piwoni.size())/ 2];
            DFS2(i);
        }
        wx = - 10000;
    }

    for (int i = 1; i <= n; i ++) {
        //cout << w[i].st << " " << w[i].nd << "\n";
    }

    if (ok) {
        cout << "YES\n";
        for (int i = 1; i <= n; i ++) {
            cout << c[i] << " ";
        }
        cout << "\n";
    } else {
        cout << "NO\n";
    }

    return 0;
}

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