Submission #1278942

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278942		nikolashami	Graph (BOI20_graph)	C++20	0 / 100	1 ms	340 KiB

Graph

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

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});
        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){
        par[lik]=lik;
        fill(par,par+n+2,-1);
        fill(cl,cl+n+2,0);
        dfs(lik);
        vector<ll>cyc;
        ll t=par[lik];
        cyc.push_back(lik);
        while(t!=lik&&t!=-1){
            cyc.push_back(t);
            t=par[t];
        }
        assert(t!=-1);
        //for(ll x:cyc)cout<<x<<'\n';
        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';
        }*/
    }
}

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