Submission #1326878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326878		bearrbearr	Graph (BOI20_graph)	C++20	100 / 100	185 ms	25384 KiB

Graph

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair<int,int>
#define fir first
#define sec second
#define pb push_back

const int maxn=1e5+2;

int n,m;
vector<ii>adj[maxn];
bool vis[maxn];
int col[maxn],val[maxn];
vector<int>msk;
bool bip;
int sh;

void dfs(int cur){
    vis[cur]=true;
    msk.pb(cur);

    for(auto [v,w]: adj[cur]){
        if(vis[v]){
            if(col[v]==col[cur]){
                bip=false;
                sh=(w-(val[cur]+val[v]))/2;
                //cout<<v<<" "<<cur<<" "<<sh<<endl;
                sh*=col[cur];
            }
        
        }
        else{
            col[v]=-col[cur];
            val[v]=w-val[cur];
            dfs(v);
        }
    }
}

int ans[maxn];

signed main(){
    cin>>n>>m;
    for(int q=1;q<=m;q++){
        int u,v,w;
        cin>>u>>v>>w;
        w*=2;
        adj[u].pb({v,w});
        adj[v].pb({u,w});
    }
    for(int q=1;q<=n;q++){
        if(vis[q])continue;
        msk.clear(),bip=true,sh=0;
        col[q]=1;
        dfs(q);

        if(bip){
            vector<int>isi;
            for(auto x : msk){
                isi.pb(-val[x]*col[x]);
            }
            sort(isi.begin(),isi.end());
            sh=isi[isi.size()/2];
        }
        
        for(auto x : msk){
            for(auto [y,w] : adj[x]){
                int vx=val[x]+col[x]*sh,vy=val[y]+col[y]*sh;
                if(vx+vy!=w){
                    cout<<"NO"<<endl; return 0;
                }
            }
            ans[x]=val[x]+col[x]*sh;
        }
    }
    cout<<"YES"<<endl;
    for(int q=1;q<=n;q++){
        double hmm=ans[q]/2.0;
        cout<<fixed<<setprecision(2)<<hmm<<' ';
    }
    cout<<endl;
}

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