Submission #1278944

#TimeUsernameProblemLanguageResultExecution timeMemory
1278944nikolashamiGraph (BOI20_graph)C++20
0 / 100
1 ms340 KiB
#include<bits/stdc++.h>
using namespace std;
using ll=long long;

const ll N=1e5+7;
vector<array<ll,2>>g[N];
double W[N];
ll par[N],cl[N],n,m,lik;

void dfs(ll u){
    if(u==lik&&cl[lik])return;
    cl[u]=1;
    for(auto[v,w]:g[u]){
        if(cl[v]&&v!=lik)continue;
        par[v]=u;
        dfs(v);
    }
}

bool odradi(ll poc){
    queue<ll>q;
    q.push(poc);
    while(!q.empty()){
        ll u=q.front();
        q.pop();
        for(auto[v,w]:g[u]){
            if(W[v]!=-2e9){
                double zb=W[v]+W[u];
                double lik=w;
                if(abs(zb-lik)>1e-7)return 0;
            }else{
                W[v]=(double)w-W[u];
                q.push(v);
            }
        }
    }
    return 1;
}

vector<array<ll,2>>E;
ll tp[N],dp[N];

vector<ll>nadji(ll poc){ //prvi na ret je on
    queue<ll>q;
    q.push(poc);
    fill(dp,dp+n+2,-1);
    fill(tp,tp+n+2,-1);
    fill(par,par+n+2,-1);
    tp[poc]=poc;
    dp[poc]=0;
    while(!q.empty()){
        ll u=q.front();q.pop();
        for(auto[v,w]:g[u]){
            if(dp[v]!=-1)continue;
            dp[v]=dp[u]+1;
            q.push(v);
            par[v]=u;
            tp[v]=(u==poc?v:tp[u]);
        }
    }
    for(auto[u,v]:E){
        if(!(dp[u]>=0&&dp[v]>=0&&tp[u]!=tp[v]&&(dp[u]&1)==(dp[v]&1)))continue;
        vector<ll>p1,p2;
        for(ll t=u;t!=-1;t=par[t])p1.push_back(t);
        for(ll t=v;t!=-1;t=par[t])p2.push_back(t);
        reverse(p1.begin(),p1.end());
        for(ll x:p2)p1.push_back(x);
        p1.pop_back();
        return p1;
    }
    return{};
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    //ako stavim da mi je neki cvor u = delta, onda su svi cvorovi unikatno odr
    //znaci ono sto mi je problem ovde u sustini su ciklusi
    //da li je za ciklus unikatno odredjen broj koji radi?
    //ako je ciklus neparne duzine unikatno je odredjeno
    //ako je paran ili radi za svaki ili ne radi uopste
    //za ako imam neparni slucaj je trivijaln samo ga odradim
    //a ako je graf bipartitivan, lupim da mi je neki lik nesto i probam

    map<array<ll,2>,ll>mp;

    cin>>n>>m;
    for(int i=1,u,v,w;i<=m;++i){
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
        E.push_back({u,v});
        if(mp[{u,v}])continue;
        mp[{u,v}]=mp[{v,u}]=w;
    }

    fill(cl,cl+n+1,-1);
    cl[1]=0;
    queue<ll>q;
    q.push(1);

    lik=-1;
    while(!q.empty()){
        ll u=q.front();
        q.pop();
        for(auto[v,w]:g[u]){
            if(cl[v]!=-1){
                if(cl[v]==cl[u])lik=v;
            }else{
                cl[v]=cl[u]^1;
                q.push(v);
            }
        }
    }

    if(lik!=-1){
        vector<ll>cyc=nadji(lik);
        //for(ll x:cyc)cout<<x<<' ';
        //return 0;
        ll delta=0;
        for(int i=1;i<cyc.size();++i)
            delta+=(mp[{cyc[i-1],cyc[i]}])*(i&1?-1:1);
        double alfa=((double)(mp[{cyc.front(),cyc.back()}]-delta))/2.0;
        for(int i=0;i<n+4;++i)W[i]=-2e9;
        W[lik]=alfa;
        bool ok=odradi(lik);
        if(!ok){
            cout<<"NO\n";
        }else{
            cout<<"YES\n";
            for(int i=1;i<=n;++i)
                cout<<fixed<<setprecision(6)<<W[i]<<' ';
        }
        return 0;
    }else{
        //uvek min u 0? ako ne moze vrv ternarna
        for(int i=0;i<n+4;++i)W[i]=-2e9;
        W[1]=0;
        bool ok=odradi(1);
        if(!ok){
            cout<<"NO\n";return 0;
        }else{
            cout<<"YES\n";
            for(int i=1;i<=n;++i)
                cout<<fixed<<setprecision(6)<<W[i]<<' ';
        }
        /*for(double i=-4;i<=4;i+=0.1){
            for(int i=0;i<n+4;++i)W[i]=-2e9;
            W[1]=i;
            odradi(1);
            double ans=0;
            for(int i=1;i<=n;++i)ans+=max(W[i],-W[i]);
            cout<<fixed<<setprecision(6)<<i<<' '<<ans<<'\n';
        }*/
    }
}
#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...