Submission #1145477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145477		Ludissey	Graph (BOI20_graph)	C++17	100 / 100	102 ms	24264 KiB

Graph

#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long
using namespace std;

vector<pair<bool,double>> val; // le teken de x(false = -1 ||true = 1) et b
vector<double> out; 
vector<int> med;
vector<vector<pair<int,int>>> neigh;
vector<int> visited;
double valeurDOFFICE=1e9;
bool possible=true;

void dfs(int x, bool tt, double b){
    if(visited[x]==1){
        if(val[x]==make_pair(tt,b)) return;
        if(val[x].first==tt) { possible=false; return; }
        else{
            double b1=val[x].second;
            double b2=b;
            if(tt==false) swap(b1,b2);
            valeurDOFFICE=(b1-b2)/(double)2;
            return;
        }
    }
    visited[x]=1;
    val[x]={tt,b};
    if(tt) med.push_back(-b);
    else med.push_back(b);
    for (auto u : neigh[x])
    {
        dfs(u.first,!tt,u.second-b);
        if(possible==false||valeurDOFFICE<1e9){
            return;
        }
    }
    
}

void setVAL(int x, double vl){
    if(visited[x]==2){
        if(abs(vl-out[x])>0.0000001) {
            possible=false;
        }
        return;
    };
    out[x]=vl;
    visited[x]=2;
    for (auto u : neigh[x]) setVAL(u.first,(double)u.second-vl);
}


signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n,m; cin >> n >> m;
    visited.resize(n,0);
    neigh.resize(n);
    out.resize(n);
    val.resize(n);
    for (int i = 0; i < m; i++)
    {
        int u,v,c; cin >> u >> v >> c; u--; v--;
        neigh[u].push_back({v,c});
        neigh[v].push_back({u,c});
    }
    for (int i = 0; i < n; i++)
    {
        if(visited[i]>0) continue;
        med.clear();
        valeurDOFFICE=1e9;
        dfs(i,true,0);
        if(!possible) break;
        if(valeurDOFFICE==1e9){
            sort(all(med));
            valeurDOFFICE=(med[(sz(med)-1)/2]+med[sz(med)/2])/2;
        }
        setVAL(i,valeurDOFFICE);
    }
    if(possible){
        cout << "YES\n";
        for (int i = 0; i < n; i++)
        {
            cout << setprecision(7) <<  out[i] << " ";
        }
    }else{
        cout << "NO\n";
    }
    return 0;
}

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