Submission #781132

#	Time	Username	Problem	Language	Result	Execution time	Memory
781132		FEDIKUS	Graph (BOI20_graph)	C++17	58 / 100	1082 ms	20216 KiB

Graph

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const ll maxn=1e5+10;

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

void dfs(ll node){
    comp.push_back(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(){
    ll n,m;
    cin>>n>>m;
    for(ll i=0;i<m;i++){
        ll u,v,c;
        cin>>u>>v>>c;
        g[u].push_back({v,c});
        g[v].push_back({u,c});
    }
    for(int i=1;i<=n;i++){
        if(vis[i]) continue;
        sgn[i]=1;
        val[i]=0;
        comp.clear();
        a.clear();
        dfs(i);
        if(a.size()>1) moze=false;
        if(a.size()==1){
            double aa=*a.begin();
            for(ll i:comp){
                res[i]=aa*sgn[i]/2+val[i];
            }
            continue;
        }
        ll best=0;
        ll curr=LLONG_MAX;
        for(ll i:comp){
            ll sum=0;
            for(ll j:comp){
                sum+=abs(val[j]+val[i]*sgn[j]);
            }
            if(sum<curr){
                curr=sum;
                best=val[i];
            }
        }
        for(ll i:comp){
            ll sum=0;
            for(ll j:comp){
                sum+=abs(val[j]-val[i]*sgn[j]);
            }
            if(sum<curr){
                curr=sum;
                best=-val[i];
            }
        }
        for(ll i:comp){
            res[i]=val[i]+best*sgn[i];
        }
    }
    if(moze){
        cout<<"YES\n";
        cout<<fixed<<showpoint<<setprecision(15);
        for(int i=1;i<=n;i++){
            cout<<res[i];
            cout<<" ";
        }
    }else cout<<"NO\n";
    return 0;
}

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