Submission #1303444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303444		BuiDucManh123	Graph (BOI20_graph)	C++20	0 / 100	1 ms	340 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 = 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});
    }

    vector<double> val = {-2, -1.5, -1.0, -0.5, 0, 0.5, 1, 1.5, 2};
    for(int i = 1; i <= n; i++){
        if(vis[i]) continue;
        double now = inf;
        double pos = inf;
        for(double x : val){
            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;
}

Compilation message (stderr)

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

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