Submission #1260364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260364		anteknne	Graph (BOI20_graph)	C++20	17 / 100	15 ms	2632 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];
int c[MAXN];
int C[MAXN];
bool odw[MAXN];
bool ODW[MAXN];
vector<int> vec;
vector<int> kand;
int n;

void DFS (int v) {
    vec.pb(v);
    for (auto x : graf[v]) {
        if (!odw[x.st]) {
            odw[x.st] = true;
            c[x.st] = x.nd - c[v];
            DFS(x.st);
        }
    }
}

bool licz (int v, int x) {
    vec.clear();

    c[v] = x;
    odw[v] = true;
    DFS(v);

    for (auto i : vec) {
        for (auto x : graf[i]) {
            if (c[i] + c[x.st] != x.nd) {
                return false;
            }
        }
    }

    return true;
}

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

    for (int i = 0; i <= 10 * 1000 * 1000; i += 500 * 1000) {
        kand.pb(i);
        kand.pb(-i);
    }

    int m;
    cin >> n >> m;

    int a, b, r;
    for (int i = 0; i < m; i ++) {
        cin >> a >> b >> r;

        graf[a].pb({b, r * 1000 * 1000});
        graf[b].pb({a, r * 1000 * 1000});
    }

    int cnt = 0;
    for (int i = 1; i <= n; i ++) {
        c[i] = INF;
    }

    if (n <= 1000) {
        for (int v = 1; v <= n; v ++) {
            if (int(graf[v].size()) == 0) {
                ODW[v] = true;
                cnt ++;
                C[v] = 0;
                continue;
            }

            for (auto i : kand) {
                if (licz(v, i)) {
                    if (!ODW[v]) {
                        for (auto x : vec) {
                            ODW[x] = true;

                            C[x] = c[x];
                            cnt ++;
                        }
                    } else {
                        int abs1 = 0;
                        int abs2 = 0;
                        for (auto x : vec) {
                            abs1 += abs(C[x]);
                            abs2 += abs(c[x]);
                        }
                        if (abs2 < abs1) {
                            for (auto x : vec) {
                                C[x] = c[x];
                            }
                        }
                    }
                }
                for (auto x : vec) {
                    c[x] = INF;
                    odw[x] = false;
                }
            }
        }

        if (cnt == n) {
            cout << "YES\n";
            for (int i = 1; i <= n; i ++) {
                cout << ld(C[i])/ld(1000 * 1000) << " ";
            }
            cout << "\n";
        } else {
            cout << "NO\n";
        }
    } else {
        for (int v = 1; v <= n; v ++) {
            if (ODW[v]) {
                continue;
            }

            if (int(graf[v].size()) == 0) {
                ODW[v] = true;
                cnt ++;
                C[v] = 0;
                continue;
            }


            for (auto i : kand) {
                if (ODW[v]) {
                    continue;
                }

                if (licz(v, i)) {
                    for (auto x : vec) {
                        ODW[x] = true;

                        C[x] = c[x];
                        cnt ++;
                    }
                }
                for (auto x : vec) {
                    c[x] = INF;
                    odw[x] = false;
                }
            }

            if (!ODW[v]) {
                break;
            }

        }

        if (cnt == n) {
            cout << "YES\n";
            for (int i = 1; i <= n; i ++) {
                cout << ld(C[i])/ld(1000 * 1000) << " ";
            }
            cout << "\n";
        } else {
            cout << "NO\n";
        }
    }



    return 0;
}

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