Submission #1186618

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186618		Francisco_Martin	Graph (BOI20_graph)	C++20	100 / 100	114 ms	30396 KiB

Graph

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

#define debug(v) cerr<<#v" = "<<(v)<<"\n";
#define debugvec(v) do{cerr<<#v<<" = [";for(int i=0;i<v.size();i++)cerr<<v[i]<<(i==v.size()-1?"":", ");cerr<<"]\n";}while(0);
#define debugvecp(v) do{cerr<<#v<<" = [";for(int i=0;i<v.size();i++)cerr<<"[ "<<v[i].fst.fst<<" "<<v[i].fst.snd<<" ]"<<(i==v.size()-1?"":", ");cerr<<"]\n";}while(0);
#define fst first
#define snd second
#define gcd(x,y) __gcd(x,y)
#define OnlineJudge(s) freopen((s".in"),"r",stdin); freopen((s".out"),"w",stdout);
#define fastIO() cin.tie(0)->sync_with_stdio(0);cin.exceptions(cin.failbit);
#define boolsolve() cout<<(solve()?"Yes":"No");

using ll=long long;
using ull=unsigned long long;
using pll=pair<ll,ll>;
using vll=vector<ll>;
using vpll=vector<pll>;
using vvll=vector<vll>;

const ll INF=1e8;
const ll MOD=1e9+7;
const ll MAXN=2e5+1;

vector<bool> vis(MAXN,false); bool flag=true, flag2=false; pll xf;
vll  B; vpll g[MAXN], A(MAXN);

void dfs(ll v,ll p){
    vis[v]=true;
    B.push_back(v);
    for(auto u:g[v]){
        if(u.fst==p) continue;
        pll x={-A[v].fst,u.snd-A[v].snd};
        if(!vis[u.fst]){
            A[u.fst]=x;
            dfs(u.fst,v);
        }else{
            if(x.fst==A[u.fst].fst){
                if(x.snd!=A[u.fst].snd){
                    flag=false;
                    return;
                }
            }else{
                pll x2={x.fst-A[u.fst].fst,A[u.fst].snd-x.snd};
                if(!flag2){
                    xf=x2;
                    flag2=true;
                }else if(xf.fst*x2.snd!=xf.snd*x2.fst){
                    flag=false;
                    return;
                }
            }
        }
    }
}

double ok(double k){
    double res=0;
    for(int v:B) res+=abs(k*A[v].fst+A[v].snd);
    return res;
}

void solve(){
    ll n, m, a, b, c; double l, r; vector<double> ans(MAXN);
    cin >> n >> m;
    for(int i=0; i<m; i++){
        cin >> a >> b >> c;
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }
    for(int i=1; i<=n && flag; i++){
        if(!vis[i]){
            flag2=false;
            B.clear();
            A[i]={1,0};
            dfs(i,-1);
            double y=0;
            if(flag2) y=(double)xf.snd/xf.fst;
            else{
                l=-INF, r=INF;
                while(abs(r-l)>1e-10){
                    double m1=l+(r-l)/3.0, m2=r-(r-l)/3.0;
                    if(ok(m1)>ok(m2)) l=m1;
                    else r=m2;
                }
                y=l;
            }
            for(int v:B) ans[v]=y*A[v].fst+A[v].snd;
        }
    }
    if(!flag) cout << "NO";
    else{
        cout << "YES\n";
        for(int i=1; i<=n; i++) cout << ans[i] << " ";
    }
}

int main(){
    fastIO();
    cout.setf(ios::fixed);
    cout.precision(7);
    //OnlineJudge("")
    ll t=1;
    //cin >> t;
    while(t--){
        solve();
        //cout << "\n";
    }
    return 0;
}

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