Submission #1299564

#TimeUsernameProblemLanguageResultExecution timeMemory
1299564efegGraph (BOI20_graph)C++20
100 / 100
538 ms89900 KiB
#include <bits/stdc++.h>
using namespace std;

#define all(v) v.begin(),v.end()
#define F first 
#define S second
#define pb push_back
#define eb emplace_back
#define ld long double

typedef pair<int,ld> ii; 

using i64 = long long;
template<typename T>
using vec = vector<T>; 

int n,m; 
vec<vec<ii>> adj;
map<ii,int> mp; 
vec<ii> state;
vec<int> par,vis; 
vec<int> comp; 
vec<ld> xvals; 

bool ok = true; 

void dfs(int node){
    if (vis[node]) return; 
    vis[node] = true; 
    comp.pb(node); 
    
    int a; ld b; tie(a,b) = state[node]; 
    
    for (auto tp : adj[node]){
        int to,w; tie(to,w) = tp; 
        int nwa = -a; 
        ld nwb = w - b;
        
        if (!vis[to]){
            par[to] = node; 
            state[to] = {nwa,nwb}; 
            dfs(to); 
        }
        
        int toa; ld tob; tie(toa,tob) = state[to]; 
        
        if ((toa == nwa && tob == nwb) || toa == 0) continue; 
        else if (toa == nwa){
            ok = false; 
        }
        else {
            ld x = (nwb - tob) / (toa - nwa); 
            xvals.pb(x); 
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); 
    cout << fixed << setprecision(10); 
    cin >> n >> m; 
    adj.assign(n + 10,vec<ii>()); 
    state.assign(n + 10,ii(0,0)); 
    vis.assign(n + 10,0); 
    par.assign(n + 10,-1); 


    for (int i = 0; i < m; i++){
        int a,b,v; cin >> a >> b >> v; 
        a--; b--; 
        adj[a].eb(b,v); 
        adj[b].eb(a,v); 
        if (mp.count({a,b}) && mp[{a,b}] != v) ok = false; 
        mp[{a,b}] = v; 
        mp[{b,a}] = v; 
    }

    for (int i = 0; i < n; i++){
        if (!vis[i]){
            comp.clear(); 
            xvals.clear(); 
            state[i] = {1,0}; 
            dfs(i); 
            ld x;
            
            if (!xvals.empty()){
                x = xvals[0];
                for (int i = 1; i < xvals.size(); i++){
                    if (xvals[i] != x) {
                        ok = false; 
                        break; 
                    }
                }
            }
            else {
                vec<ld> v; 
                for (auto node : comp){
                    if (state[node].F == -1) v.pb(state[node].S); 
                    else if (state[node].F == 1) v.pb(-state[node].S); 
                }
                if (v.empty()) continue; 
    
                sort(all(v));
    
                if (v.size() % 2) x = v[v.size() / 2]; 
                else x = (v[v.size() / 2] + v[v.size() / 2 - 1]) / 2; 
            }

            for (auto node : comp){
                if (state[node].F == 0) continue;
                state[node] = {0, state[node].F * x + state[node].S}; 
            }
        } 
    }

    if (!ok) cout << "NO" << endl;
    else {
        cout << "YES" << endl; 
        for (int i = 0; i < n; i++){
            cout << state[i].S << " "; 
        }
    }

    return 0; 
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...