Submission #651367

#	Time	Username	Problem	Language	Result	Execution time	Memory
651367		1zaid1	Graph (BOI20_graph)	C++17	0 / 100	19 ms	35660 KiB

Graph

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n';

const int M = 5e5+5, MOD = 1e9+7;
vector<array<int, 3>> v;
int p[M], d[M], loop;
vector<int> node[M];
bitset<500005> vis;
map<int, int> e[M];
double cost[M];

void dfs(int s, int dp = 0) {
    vis[s] = 1;
    d[s] = dp++;

    for (int i:node[s]) {
        if (!vis[i]) {
            p[i] = s;
            dfs(i, dp);
        } else if ((dp-d[i])%2) {
            p[i] = s;
            loop = s;
            return;
        }
    }
}

double eval(int s, double a) {
    double ans = a;
    cost[s] = a;
    vis[s] = 1;
    for (int i:node[s]) if (!vis[i]) ans += abs(eval(i, e[s][i]-a));
    return ans;
}

bool check() {
    for (auto [a, b, c]:v) if (cost[a] + cost[b] != c) return 0;
    return true;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if (e[a][b] && e[a][b] != c) {
            cout << "NO" << endl;
            return 0;
        }

        e[a][b] = c;
        e[b][a] = c;
        node[a].push_back(b);
        node[b].push_back(a);
        v.push_back({a, b, c});
    }

    dfs(1);
    if (loop) {
        int x = p[loop], y = loop, f = 0;
        double sum = e[x][y];
        do {
            y = x, x = p[x];
            if (f) sum += e[x][y];
            else sum -= e[x][y];
            f ^= 1;
        } while (x != loop);

        vis = 0;
        eval(loop, sum/2);
        // cout << "LOOP " << loop << endl;
    } else {
        vis = 0;
        eval(1, 0);
        if (!check()) {
            cout << "NO" << endl;
            return 0;
        }

        double l = -1e10, r = 1e10;
        while (r-l >= 1e-6) {
            double ll = (2*l+r)/3;
            double rr = (l+2*r)/3;
            vis = 0; double x = eval(1, ll);
            vis = 0; double y = eval(1, rr);
            if (x > y) l = ll;
            else r = rr;
        } vis = 0, eval(1, r);
        // cout << "NO LOOP" << endl;
    }

    vis = 0;
    if (!check()) {
        cout << "NO" << endl;
        return 0;
    }

    cout << "YES" << fixed << setprecision(6) << endl;
    for (int i = 1; i <= n; i++) cout << cost[i] << ' '; cout << endl;

    return 0;
}

/*
4 4
1 2 1
2 3 2
1 3 2
3 4 1

2 1
1 2 1

3 2
1 2 2
2 3 2

3 4
1 2 2
2 2 1
2 1 1
1 2 2
*/

Compilation message (stderr)

Graph.cpp: In function 'int main()':
Graph.cpp:105:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  105 |     for (int i = 1; i <= n; i++) cout << cost[i] << ' '; cout << endl;
      |     ^~~
Graph.cpp:105:58: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  105 |     for (int i = 1; i <= n; i++) cout << cost[i] << ' '; cout << endl;
      |                                                          ^~~~

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