Submission #1290268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290268		mhn_neek	Graph (BOI20_graph)	C++20	100 / 100	82 ms	13868 KiB

Graph

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    if(!(cin >> N >> M)) return 0;
    vector<vector<pair<int,int>>> adj(N+1);
    for(int i=0;i<M;i++){
        int a,b,c; cin >> a >> b >> c;
        adj[a].push_back({b,c});
        if(a!=b) adj[b].push_back({a,c}); // if self-loop, add once, but we will still process it
        else {
            // for a self-loop we keep a single entry; processing logic handles it
        }
    }

    const long double EPS = 1e-9L;
    vector<int> s(N+1, 0);               // sign: +1 or -1 (0 = unvisited)
    vector<long double> b(N+1, 0.0L);    // constant term x_i = s_i * t + b_i
    vector<long double> ans(N+1, 0.0L);

    for(int start = 1; start <= N; ++start){
        if(s[start] != 0) continue;
        // BFS this component
        queue<int> q;
        vector<int> comp;
        s[start] = 1;
        b[start] = 0.0L;
        q.push(start);
        comp.push_back(start);

        bool impossible = false;
        bool t_fixed = false;
        long double t_value = 0.0L;

        while(!q.empty() && !impossible){
            int u = q.front(); q.pop();
            for(auto [v, wint] : adj[u]){
                long double w = (long double)wint;
                if(s[v] == 0){
                    s[v] = -s[u];
                    b[v] = w - b[u];
                    q.push(v);
                    comp.push_back(v);
                } else {
                    if(s[v] == -s[u]){
                        // must have b[u] + b[v] == w
                        if(fabsl(b[u] + b[v] - w) > EPS){
                            impossible = true;
                            break;
                        }
                    } else {
                        // s[v] == s[u] -> determines t
                        // (s_u + s_v) * t + b_u + b_v = w
                        // sum = 2*s[u]
                        long double denom = 2.0L * (long double)s[u];
                        long double cand = (w - b[u] - b[v]) / denom;
                        if(!t_fixed){
                            t_fixed = true;
                            t_value = cand;
                        } else {
                            if(fabsl(t_value - cand) > 1e-7L){ // slightly larger tolerance for multiple constraints
                                impossible = true;
                                break;
                            }
                        }
                    }
                }
            }
        }
        if(impossible){
            cout << "NO\n";
            return 0;
        }

        if(t_fixed){
            // compute ans for component using fixed t_value
            for(int v : comp){
                ans[v] = (long double)s[v] * t_value + b[v];
            }
        } else {
            // choose t as median of values z_i = - s_i * b_i
            vector<long double> values;
            values.reserve(comp.size());
            for(int v: comp) values.push_back(- (long double)s[v] * b[v]);
            sort(values.begin(), values.end());
            long double t;
            int k = (int)values.size();
            if(k % 2 == 1){
                t = values[k/2];
            } else {
                // any value between values[k/2 - 1] and values[k/2] works; choose their average
                t = (values[k/2 - 1] + values[k/2]) / 2.0L;
            }
            for(int v: comp){
                ans[v] = (long double)s[v] * t + b[v];
            }
        }
    }

    // final verification (optional, but good): check every edge's sum and output
    // We skip heavy checking for speed, but could check and reject if something off.

    cout.setf(std::ios::fixed); cout << setprecision(10);
    cout << "YES\n";
    for(int i=1;i<=N;i++){
        if(i>1) cout << ' ';
        double out = (double)ans[i];
        cout << out;
    }
    cout << '\n';
    return 0;
}

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