Submission #1299563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299563		efeg	Graph (BOI20_graph)	C++20	0 / 100	1 ms	344 KiB

Graph

#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; 

bool ok = true; 

void dfs(int node){
    if (vis[node]) return; 
    vis[node] = 1;
    comp.pb(node); 
    
    int a; ld b; tie(a,b) = state[node]; 
    
    for (auto tp : adj[node]){
        int to,w; tie(to,w) = tp; 
        if (vis[to] == 2) continue;
        
        int toa; ld tob; tie(toa,tob) = state[to]; 
        tie(a,b) = state[node]; 
        
        int nwa = -a; 
        ld nwb = w - b;
        if (vis[to] == 1){
            if ((toa == nwa && tob == nwb) || toa == 0) continue; 
            else if (toa == nwa){
                ok = false; 
            }
            else {
                ld x = (nwb - tob) / (toa - nwa); 
                
                int curr = node; 
                while (1){
                    int tmpa; ld tmpb; tie(tmpa,tmpb) = state[curr]; 
                    if (tmpa != 0){
                        ld v = tmpa * x + tmpb; 

                        state[curr] = {0,v}; 
                    }
                    if (curr == to) break; 
                    curr = par[curr]; 
                }                
            }
        }
        else {
            par[to] = node; 
            state[to] = {nwa,nwb}; 
            dfs(to); 
        }        
    
    }

    vis[node] = 2; 
}

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(); 
            state[i] = {1,0}; 
            dfs(i); 

            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));

            ld x; 
            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; 
}

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