Submission #1182221

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182221		qwusha	Graph (BOI20_graph)	C++20	34 / 100	1095 ms	2372 KiB

Graph

#include <bits/stdc++.h>
using namespace std;
/*
#pragma GCC optimize("O3")
#include <bitset>
#pragma GCC target("avx2")*/
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
int inf = 1e15;


vector<vector<int>> g;
map<pair<int, int>, int> mp;

vector<int> val;

bool dfs(int v, int q) {
    val[v] = q;
    for (auto u : g[v]) {
        if (val[u] != inf) {
            if (val[u] + val[v] != mp[{v, u}])
                return 0;
        } else {
            int res = dfs(u, mp[{v, u}] - val[v]);
            if (res == 0)
                return 0;
        }
    }
    return 1;
}

vector<int> col;

void dfs_comp(int v, int c) {
    col[v] = c;
    for (auto u : g[v]) {
        if (col[u] == -1) {
            dfs_comp(u, c);
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    g.resize(n);
    for (int i = 0; i < m; i++) {
        int v, u, w;
        cin >> v >> u >> w;
        g[v - 1].push_back(u - 1);
        g[u - 1].push_back(v - 1);
        if (mp.find({v - 1, u - 1}) != mp.end()) {
            if (mp[{v - 1, u - 1}] != w * 2) {
                cout << "NO" << '\n';
                return 0;
            }
        } else {
            mp[{v - 1, u - 1}] = w * 2;
            mp[{u - 1, v - 1}] = w * 2;
        }
    }
    col.resize(n, -1);
    vector<int> boss;
    for (int i = 0; i < n; i++) {
        if (col[i] == -1) {
            boss.push_back(i);
            dfs_comp(i, boss.size() - 1);
        }
    }
    vector<vector<int>> comps(boss.size());
    for (int i = 0; i < n; i++) {
        comps[col[i]].push_back(i);
    }
    val.assign(n, inf);
    bool done = 1;
    int answer = 0;
    vector<int> bq(boss.size());
    for (int co = 0; co < boss.size(); co++) {
        bool ok = 0;
        int best = inf;
        int indb = -1;
        for (int q = -1000; q <= 1000; q++) {
            for (auto el : comps[co]) {
                val[el] = inf;
            }
            if (dfs(boss[co], q)) {
                ok = 1;
                int sum = 0;
                for (auto el : comps[co])
                    sum += abs(val[el]);
                if (sum < best) {
                    best = sum;
                    indb = q;
                }
            }
        }
        bq[co] = indb;
        if (ok == 0) {
            done = 0;
            break;
        }
        answer += best;
    }
    if (done == 0) {
        cout << "NO" << '\n';
        return 0;
    } else {
        cout << "YES" << '\n';
        for (int i = 0; i < n; i++) {
            val[i] = inf;
        }
        for (int co = 0; co < boss.size(); co++) {
            dfs(boss[co], bq[co]);
        }
        for (auto el : val) {
            cout << el * 0.5 << ' ';
        }
        cout << '\n';
    }


}

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