Submission #1278967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278967		nikolashami	Graph (BOI20_graph)	C++20	17 / 100	3 ms	592 KiB

Graph

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

#pragma GCC optimize("O3")
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);
    
    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;
        if(mp[{u,v}]){
        	if(mp[{u,v}]!=w)F=1;
        	else continue;
        }
        g[u].push_back({v,w});
        g[v].push_back({u,w});
        E.push_back({u,v});
        mp[{u,v}]=mp[{v,u}]=w;
    }

    //if(n==1&&m==1&&mp[{1,1}]==1){
    //	cout<<"YES\n0.5";return 0;
    //}

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

	    //cout<<K<<endl;

	    if(mp[{lik,lik}]){
	    	for(int i=0;i<n+4;++i)W[i]=-2e9;
	    	W[lik]=(double)mp[{lik,lik}]/2.0;
	    	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 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);
	        double klk=0;
	        for(int i=1;i<=n;++i){
	        	if(W[i]!=-2e9)klk+=abs(W[i]);
	        }
	        ll naj=0;
	        for(int j=0;j<=40;++j){
	        	for(int i=0;i<n+4;++i)W[i]=-2e9;
		        W[K]=j;
		        ok=odradi(K);
		        double klk2=0;
		        for(int i=1;i<=n;++i){
		        	if(W[i]!=-2e9)klk2+=abs(W[i]);
		        }
		        if(klk2<klk){
		        	klk=klk2;
		        	naj=j;
		        }
	        }
	        for(int i=0;i<n+4;++i)W[i]=-2e9;
	        W[K]=naj;
	        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]<<' ';
}

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