제출 #1338518

#제출 시각아이디문제언어결과실행 시간메모리
1338518stoneGraph (BOI20_graph)C++20
5 / 100
2 ms344 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];
vector<vector<int>>cmp;
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);
        }
    }
}
vector<int>tmp;
void fun(int a){
    tmp.pb(a);
    vis[a]=1;
    for(auto [b,c]:v[a]){
        if(vis[b]==0){
            vis[b]=1;
            fun(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});
    }
    for(int i=1;i<=n;i++){
        if(vis[i]==0){
            tmp.clear();
            fun(i);
            cmp.pb(tmp);
        }
    }
    for(auto tmp:cmp){
        int A=tmp[0];
        vector<bool>in (n+10);
        for(auto a:tmp)in[a]=1;
        vector<pair<double,double>>vt;
        for(double x=-2;x<=2; x+=0.5){
            for(int i:tmp){
                vis[i]=0;
                col[i]=0;
            }
            col[A]=x;
            dfs(A);
            bool u=1;
            for(auto vec:vc){
                int a=vec[0],b=vec[1],c=vec[2];
                if(in[a]==0)continue;
                // mna comp iin edge mun uu guyu 
                if(col[a]+col[b]!=double(c))u=0;
            }
            if(u){
                double s=0;
                for(auto i:tmp)s+=abs(col[i]);
                vt.pb({s,x});
            }
        }
        sort(vt.begin(),vt.end());
        if(vt.empty()){
            cout<<"NO"<<endl;
            return 0;
        }
        for(auto i:tmp){
            vis[i]=0;
            col[i]=0;
        }
        col[A]=vt[0].ss;
        dfs(A);
    }
    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...