Submission #779453

#	Time	Username	Problem	Language	Result	Execution time	Memory
779453		FEDIKUS	Graph (BOI20_graph)	C++17	0 / 100	2 ms	2644 KiB

Graph

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const int maxn=1e5+10;

vector<pair<int,int> > g[maxn];
bool moze=true;
bool vis[maxn];
int val[maxn];
int sgn[maxn];
set<int> a;

void dfs(int node){
    vis[node]=true;
    for(auto i:g[node]){
        if(vis[i.first]){
            if(sgn[i.first]!=sgn[node] && val[i.first]+val[node]!=i.second) moze=false;
            if(sgn[i.first]==sgn[node]){
                if(sgn[i.first]==1) a.emplace(i.second-val[node]-val[i.first]);
                else a.emplace(val[i.first]+val[node]-i.second);
            }
        }else{
            sgn[i.first]=-sgn[node];
            val[i.first]=i.second-val[node];
            dfs(i.first);
        }
    }
}

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v,c;
        cin>>u>>v>>c;
        g[u].push_back({v,c});
        g[v].push_back({u,c});
    }
    sgn[1]=1;
    val[1]=0;
    dfs(1);
    if(!moze || a.size()>1){
        cout<<"NO\n";
        return 0;
    }else cout<<"YES\n";
    if(a.size()==1){
        cout<<fixed<<showpoint<<setprecision(10);
        double aa=double(*a.begin())/2;
        for(int i=1;i<=n;i++){
            cout<<aa*sgn[i]+val[i]<<" ";
        }
        return 0;
    }
    int best=0;
    ll curr=LLONG_MAX;
    for(int i=1;i<=n;i++){
        ll sum=0;
        for(int j=1;j<=n;j++){
            sum+=abs(val[j]+val[i]*sgn[j]);
        }
        if(sum<curr){
            curr=sum;
            best=val[i];
        }
    }
    for(int i=1;i<=n;i++){
        ll sum=0;
        for(int j=1;j<=n;j++){
            sum+=abs(val[j]-val[i]*sgn[j]);
        }
        if(sum<curr){
            curr=sum;
            best=-val[i];
        }
    }
    for(int i=1;i<=n;i++){
        cout<<val[i]+best*sgn[i]<<" ";
    }
    return 0;
}

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