Submission #1370630

#TimeUsernameProblemLanguageResultExecution timeMemory
1370630eradaxGraph (BOI20_graph)C++20
100 / 100
108 ms29412 KiB
#include<bits/stdc++.h>
using namespace std;
using ld=long double;
using ll=long long;
#define int ll
signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,m;cin>>n>>m;
    vector<vector<pair<int,int>>> adj(n);
    vector<array<int,3>> a;
    {
        for(int i=0;i<m;i++){
            int u,v,c;cin>>u>>v>>c;
            u--,v--,c--;
            if(v>u)swap(u,v);
            a.push_back({u,v,c});
            adj[u].push_back({v,c});
            adj[v].push_back({u,c});
        }
        sort(begin(a),end(a));
        for(int i=0;i<ssize(a)-1;i++)if(a[i][0]==a[i+1][0]&&a[i][1]==a[i+1][1]&&a[i][2]!=a[i+1][2]){
            cout<<"NO\n";
            return 0;
        }
    }

    vector<ld> as(n);
    vector<int> vis(n);int tim=1;
    vector<pair<int,int>> eq(n);
    auto dfs=[&](auto&& self,int u,pair<int,int>e)->void{
        vis[u]=tim;
        eq[u]=e;
        for(auto[v,c]:adj[u])if(!vis[v])self(self,v,{-e.first,c+1-e.second});
    };
    for(int i=0;i<n;i++)if(!vis[i])dfs(dfs, i,{1,0}),tim++;

    vector<int> vis2(n),done(tim);
    auto asd=[&](auto&& self,int u,ld x)->void{
        vis2[u]=1;
        as[u]=eq[u].first*x+eq[u].second;
        for(auto[v,e]:adj[u])if(!vis2[v])self(self,v,x);
    };

    for(auto[u,v,c]:a){
        if(done[vis[u]])continue;
        pair<int,int> s=eq[u];
        s.first+=eq[v].first;
        s.second+=eq[v].second;

        if(!s.first&&s.second!=c+1){
            cout<<"NO\n";
            return 0;
        }

        if(!s.first&&s.second==c+1){
            continue;
        }

        ld x=((ld)(c+1)-s.second)/(ld)s.first;
        done[vis[u]]=1;
        asd(asd,u,x);
    }

    vector<int> vis3(n);
    for(int i=0;i<n;i++)if(!done[vis[i]]){
        ld strt=0;
        ld x1=-1e9;
        map<ld,ld> slp;
        auto add=[&](auto&& self,int u)->void{
            vis3[u]=1;
            ld x=((ld)-eq[u].second)/(ld)eq[u].first;
            slp[x]+=abs(eq[u].first*2);
            strt+=abs(x1*eq[u].first+eq[u].second);
            slp[x1]-=abs(eq[u].first);

            for(auto[v,e]:adj[u])if(!vis3[v])self(self,v);
        };
        add(add,i);

        ld cd=0;
        pair<ld,ld> best={strt,x1};
        for(auto[x2,dlt]:slp){
            strt+=(x2-x1)*cd;
            cd+=dlt;
            x1=x2;
            best=min(best,{strt,x1});
        }

        done[vis[i]]=1;
        asd(asd,i, best.second);
    }

    for(auto[u,v,c]:a)if(abs(as[u]+as[v]-c-1)>1e-7){
        cout<<"NO\n";
        return 0;
    }

    cout<<fixed<<setprecision(18);
    cout<<"YES\n";
    for(int i=0;i<n;i++)cout<<as[i]<<' ';
    cout<<'\n';
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...