제출 #1303448

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1303448		BuiDucManh123	Graph (BOI20_graph)	C++20	58 / 100	1097 ms	13008 KiB

Graph

#include <bits/stdc++.h>
#define TN ""
using namespace std;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const double inf = 1e9;
const double EPS = 1e-9;
double ans[200009];
bool vis[100009];
vector<pair<int, int>> g[100009];
bool e(double x, double y){
    return fabs(x - y) <= EPS;
}
bool solve(int u, double x){
    vis[u] = 1;
    ans[u] = x;
    for(pair<int, int> v : g[u]){
        if(vis[v.first]){
            if(v.second == 1){
                if(!e(ans[v.first] + x, 1.0)){
                    return 0;
                }
            }
            if(v.second == 2){
                if(!e(ans[v.first] + x, 2.0)){
                    return 0;
                }
            }
            continue;
        }
        if(v.second == 1){
            if(!solve(v.first, (double)(1.0 - x))) return 0;
        }else{
            if(!solve(v.first, (double)(2.0 - x))) return 0;
        }
    }
    return 1;
}
void reset(int u){
    vis[u] = 0;
    for(pair<int, int> v : g[u]){
        if(!vis[v.first]) continue;
        reset(v.first);
    }
}
double cal(int u){
    double res = abs(ans[u]);
    vis[u] = 1;
    for(pair<int, int> v : g[u]){
        if(vis[v.first]) continue;
        res += cal(v.first);
    }
    return res;
}
void Solve(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int u, v, c;
        cin >> u >> v >> c;
        g[u].push_back({v, c});
        g[v].push_back({u, c});
    }
    for(int i = 1; i <= n; i++){
        if(vis[i]) continue;
        double now = inf;
        double pos = inf;
        for(double x = -100.0; x <= 100.0; x += 0.5){
            bool siu = solve(i, x);
            reset(i);
            if(!siu){
                continue;
            }
            double cur = cal(i);
            reset(i);
            if(now > cur){
                now = cur;
                pos = x;
            }
        }
        if(pos == inf){
            cout << "NO";
            return;
        }
        solve(i, pos);
    }
    cout << "YES\n";
    cout << fixed << setprecision(8);
    for(int i = 1; i <= n; i++){
        cout << ans[i] << " ";
    }
}
signed main() {
    if(fopen(TN".inp", "r")){
        freopen(TN".inp", "r", stdin);
        freopen(TN".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int test = 1;
    //cin >> test;
    while(test--){
        Solve();
    }
    return 0;
}

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

Graph.cpp: In function 'int main()':
Graph.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen(TN".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Graph.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen(TN".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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