Submission #1338462

#TimeUsernameProblemLanguageResultExecution timeMemory
1338462JungPSGraph (BOI20_graph)C++20
0 / 100
1 ms344 KiB
#include<bits/stdc++.h>
using namespace std;

vector<pair<int,int>> vec[100007];
pair<int,int> coef[100007]; // ax+b
long double val;
bool visited[100007];
long double ans[100007];
vector<int> tmp;
int bfs(int x){
    queue<pair<pair<int,int>,int>> q;
    while(!q.empty()) q.pop();
    q.push({{1,0},x});
    coef[x]={1,0};
    val=-1e9;
    bool bad=false;
    tmp.clear();
    while(!q.empty()){
        int coefx=q.front().first.first;
        int coefnum=q.front().first.second;
        int node=q.front().second;
        visited[node]=true;
        tmp.push_back(node);
        q.pop();
        for(auto i:vec[node]){
            int ncoefx=-coefx;
            int ncoefnum=i.second-coefnum;
            if(coef[i.first].first || coef[i.first].second){
                long double tmp=-(coef[i.first].second-ncoefnum+0.0)/(coef[i.first].first-ncoefx);
                if(coef[i.first].first-ncoefx==0 && coef[i.first].second-ncoefnum==0) continue;
                if(val==-1e9){
                    val=tmp;
                }
                else{
                    if(val!=tmp){
                        bad=true;
                        break;
                    }
                }
            }
            else{
                coef[i.first]={ncoefx,ncoefnum};
                q.push({coef[i.first],i.first});
            }
        }
    }
    return bad;
}

long double get(long double x){
    long double cache=0;
    for(auto i:tmp){
        cache+=abs(coef[i].first*x+coef[i].second);
    }
    if(cache>0) return cache;
    else return -cache;
}
void ternary(long double a,long double b){
    long double l=a,r=b;
    while(r-l>1e-9){
        long double m1=l+(r-l)/3.00;
        long double m2=r-(r-l)/3.00;
        long double g1=get(m1);
        long double g2=get(m2);

        if(g1<g2){
            r=m2;
        }
        else{
            l=m1;
        }
    }
    for(auto i:tmp){
        ans[i]+=coef[i].first*l+coef[i].second;
    }
}
signed main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n,m; cin >> n >> m;
    for(int i=0;i<m;++i){
        int a,b,c; cin >> a >> b >> c;
        vec[a].push_back({b,c});
        vec[b].push_back({a,c});
    }
    bool bad=false;
    for(int i=1;i<=n;++i){
        if(!visited[i]){
            if(bfs(i)==1){
                cout << "NO\n";
                return 0;
            }
            else if(val!=-1e9){
                ternary(val,val);
            }
            else{
                ternary(-5,5);
            }
        }
    }

    cout << "YES\n";
    for(int i=1;i<=n;++i){
        cout << ans[i] << " ";
    }
    
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...