제출 #1072030

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1072030		belgianbot	Graph (BOI20_graph)	C++17	100 / 100	113 ms	14280 KiB

Graph

#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;

vector<vector<pair<int,int>>> adj;
vector<bool> processed;

double merge(pair<int,int> a, pair<int,int> b) {
    double nb = a.fi - b.fi;
    double nbX = b.se - a.se;
    if (!nbX) {
        if (!nb) return INT_MAX;
        else return INT_MIN;
    }
    return nb / nbX;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, M; cin >> N >> M;
    adj.resize(N);

    for (int i = 0; i < M; i++) {
        int a, b, c; cin >> a >> b >> c;
        a--, b--;;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
 
    vector<double> ans(N, INT_MAX);
    vector<pair<int,int>> value(N, {INT_MAX, INT_MAX});
    processed.resize(N, false);
    
    for (int i = 0; i < N; i++) {
        if (processed[i]) continue;

        vector<int> in = {i};
        double equation = INT_MAX;
        queue<int> q; q.push(i);
        processed[i] = true;
        value[i] = {0, 1};

        while (!q.empty()) {
            int x = q.front(); q.pop();
            for (auto [y, c] : adj[x]) {
                if (processed[y]) {
                    double sol = merge(value[y], {c - value[x].fi, -value[x].se});
                    if (sol == INT_MIN || (sol != INT_MAX && equation != sol && equation != INT_MAX)) {
                        cout << "NO\n";
                        return 0;
                    }
                    else if (sol != INT_MAX) equation = sol;
                }
                else {
                    processed[y] = true;
                    in.push_back(y);
                    value[y] = {c - value[x].fi, -value[x].se};
                    q.push(y);
                }
            }
        }

        if (equation == INT_MAX) {
            double l = -1000000.0, r = 1000000.0;
            double best, sum = INT_MAX;
            while (r - l > 0.000001) {
                double mid1 = l + (r - l) / 3.0, mid2 = r - (r - l) / 3.0;

                double res1 = 0.0, res2 = 0.0;
                for (int x : in) {
                    res1 += abs(value[x].fi + value[x].se * mid1);
                    res2 += abs(value[x].fi + value[x].se * mid2);
                }
                if (res1 < res2) {
                    r = mid2;
                    if (res1 < sum) {best = mid1; sum = res1;}
                }
                else {
                    l = mid1;
                    if (res2 < sum) {best = mid2;sum = res2;}
                }
            }
            equation = best;
        }
        for (int x : in) ans[x] = value[x].fi + equation * value[x].se;
    }
        

    cout << "YES\n";
    for (double x : ans) {
        cout << setprecision(6) << fixed << x << " ";
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Graph.cpp: In function 'int main()':
Graph.cpp:87:58: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |         for (int x : in) ans[x] = value[x].fi + equation * value[x].se;
      |                                                          ^

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