Submission #575864

#	Time	Username	Problem	Language	Result	Execution time	Memory
575864		talant117408	Graph (BOI20_graph)	C++17	34 / 100	1098 ms	27488 KiB

Graph

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'

void solve() {
    int n, m;
    cin >> n >> m;
    vector <vector <pair <int, int>>> graph(n+1);
    vector <pair <pii, int>> edges;
    for (int i = 1; i <= m; i++) {
        int a, b;
        int c;
        cin >> a >> b >> c;
        c *= 10;
        edges.pb(mp(mp(a, b), c));
        graph[a].pb(mp(b, c));
        graph[b].pb(mp(a, c));
    }   
    const int range = 301;
    vector <vector <bool>> can(n+1, vector <bool> (range, 1));
    vector <vector <int>> value(n+1, vector <int> (range)), sum(n+1, vector <int> (range));
    vector <pii> acc(n+1, mp(2e9, 0));
    
    vector <int> link(n+1), saizu(n+1, 1);
    iota(all(link), 0);
    function <int(int)> find = [&](int n) {
        if (link[n] == n) return n;
        return link[n] = find(link[n]);
    };
    function <void(int, int)> unite = [&](int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return;
        if (saizu[a] < saizu[b]) swap(a, b);
        saizu[a] += saizu[b];
        link[b] = a;
    };
    for (auto to : edges) {
        auto a = to.first.first, b = to.first.second;
        unite(a, b);
    }
    
    vector <int> used(n+1);
    function <void(int, int, int)> dfs = [&](int v, int val, int i) {
        value[v][i] = val;
        used[v] = 1;
        for (auto to : graph[v]) {
            if (used[to.first]) continue;
            dfs(to.first, to.second-val, i);
        }
    }; 
    
    set <int> reps;
    for (int i = 1; i <= n; i++) reps.insert(find(i));
    for (int j = 0; j < range; j++) {
        for (int i = 1; i <= n; i++) {
            if (i == find(i)) {
                dfs(i, (j-range/2), j);
            }
        }
        for (int i = 1; i <= n; i++) {
            sum[find(i)][j] += fabs(value[i][j]);
        }
        for (auto to : edges) {
            auto a = to.first.first, b = to.first.second;
            auto c = to.second;
            auto rep = find(a);
            if (fabs(c-value[a][j]-value[b][j]) > 1e-9) {
                can[rep][j] = 0;
            }
        }
        fill(all(used), 0);
        for (auto to : reps) {
            if (can[to][j]) {
                if (acc[to].first > sum[to][j]) {
                    acc[to].first = sum[to][j];
                    acc[to].second = j;
                }
            }
        }
    }
    int ans = 0;
    for (auto to : reps) {
        ans += acc[to].first;
    }
    if (ans >= 2e9) {
        cout << "NO" << endl;
        return;
    }
    cout << "YES" << endl;
    for (int i = 1; i <= n; i++) {
        cout << fixed << setprecision(6) << double(value[i][acc[find(i)].second])*.1 << ' ';
    }
}

int main() {
    //~ do_not_disturb
    
    int t = 1;
    //~ cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}
/*
7
4 2
5 7
3 4
6 3
1 3
4 5
*/

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