Submission #1169763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169763		purplelemon	Graph (BOI20_graph)	C++20	100 / 100	93 ms	30660 KiB

Graph

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double

const int N = 1e5 + 10;

int ES[2*N][3];
double ans, val[N];
vector<pair<int,int>> G[N];
pair<int,int> form[N];
vector<int> V;
bool mark[N], mark2[N], done;

void DFS(int v) {
    mark[v] = 1;
    V.push_back(form[v].second*(-form[v].first));
    for (auto u : G[v]) {
        if (!mark[u.first]) {
            form[u.first] = {-form[v].first, u.second-form[v].second};
            DFS(u.first);
            if (done) {
                return;
            }
        } else {
            if (form[u.first].first != form[v].first) {
                if (form[u.first].second != u.second - form[v].second) {
                    cout << "NO";
                    exit(0);
                }
            } else {
                ans = (form[u.first].second * (-form[u.first].first)) + ((u.second - form[v].second) * form[v].first);
                ans /= 2;
                done = 1;
                return;
            }
        }
    }
}

void FILL(int v) {
    mark2[v] = 1;
    mark[v] = 1;
    for (auto u : G[v]) {
        if (!mark2[u.first]) {
            val[u.first] = (double)(u.second - val[v]);
            FILL(u.first);
        }
    }
}


void solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 0;i < m;i++) {
        int a, b, c;
        cin >> a >> b >> c;
        ES[i][0] = a;
        ES[i][1] = b;
        ES[i][2] = c;
        G[a].push_back({b,c});
        G[b].push_back({a,c});
    }
    for (int i = 1;i <= n;i++) {
        if (!mark[i]) {
            form[i] = {1,0};
            done = 0;
            V.clear();
            DFS(i);
            if (done) {
                val[i] = ans;
            } else {
                sort(V.begin(),V.end());
                val[i] = V[V.size()/2];
            }
            FILL(i);
        }
    }
    for (int i = 0;i < m;i++) {
        if (val[ES[i][0]] + val[ES[i][1]] != ES[i][2]) {
            cout << "NO";
            return;
        }
    }
    cout << "YES" << endl;
    for (int i = 1;i <= n;i++) {
        cout << val[i] << ' ';
    }
}



int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
}

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