제출 #1338516

#제출 시각아이디문제언어결과실행 시간메모리
1338516stoneGraph (BOI20_graph)C++20
0 / 100
3 ms360 KiB
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define int long long
const int N=3e5+5;
vector<pair<int,int>>v[N];
double col[N];
bool vis[N];
void dfs(int a){
    vis[a]=1;
    for(auto [b,c]:v[a]){
        if(vis[b]==0){
            vis[b]=1;
            col[b]= c-col[a];
            dfs(b);
        }
    }
}
signed main(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>>vc;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        v[a].pb({b,c});
        v[b].pb({a,c});
        vc.pb({a,b,c});
    }
    vector<pair<double,double>>vt;
    for(double x=-2;x<=2; x+=0.5){
        for(int i=1;i<=n;i++){
            vis[i]=0;
            col[i]=0;
        }
        col[1]=x;
        dfs(1);
        bool u=1;
        for(auto vec:vc){
            int a=vec[0],b=vec[1],c=vec[2];
            if(col[a]+col[b]!=double(c))u=0;
        }
        if(u){
            double s=0;
            for(int i=1;i<=n;i++){
                s+=abs(col[i]);
            }
            vt.pb({s,x});
        }
    }
    sort(vt.begin(),vt.end());
    if(vt.empty()){
        cout<<"NO"<<endl;
        return 0;
    }
    for(int i=1;i<=n;i++){
        vis[i]=0;
        col[i]=0;
    }
    col[1]=vt[0].ss;
    dfs(1);
    cout<<"YES"<<endl;
   for(int i=1;i<=n;i++)cout<<col[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...