Submission #1278949

#TimeUsernameProblemLanguageResultExecution timeMemory
1278949nikolashamiGraph (BOI20_graph)C++20
0 / 100
1 ms468 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],WANS[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;

    ll F=0;

    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}]){F=1;}
        mp[{u,v}]=mp[{v,u}]=w;
    }

    if(F){
        cout<<"NO";return 0;
    }

    fill(cl,cl+n+1,-1);
    for(int K=1;K<=n;++K){
    	if(cl[K]!=-1)continue;
    	cl[K]=0;
    	queue<ll>q;
    	q.push(K);
    	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";
	            return 0;
	        }else{
	            for(int i=1;i<=n;++i){
	            	if(W[i]!=-2e9)WANS[i]=W[i];
	            }
	        }
	    }else{
	        //uvek min u 0? ako ne moze vrv ternarna
	        for(int i=0;i<n+4;++i)W[i]=-2e9;
	        W[K]=0;
	        bool ok=odradi(K);
	        if(!ok){
	            cout<<"NO";return 0;
	        }else{
	            for(int i=1;i<=n;++i){
	            	if(W[i]!=-2e9)WANS[i]=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';
	        }*/
	    }
    }

    cout<<"YES\n";
    for(int i=1;i<=n;++i)cout<<fixed<<setprecision(6)<<WANS[i]<<' ';
}
#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...