제출 #1288610

#제출 시각아이디문제언어결과실행 시간메모리
1288610hom84287Graph (BOI20_graph)C++17
0 / 100
2 ms3396 KiB
#include<bits/stdc++.h>
using namespace std;
#define ff first 
#define ss second
const int maxn = 1e5+123 ;
const int INF = 1e9+7 ; 
vector <pair<int,int>> adj[maxn] ;
int n,m,h[maxn],mol[maxn];
double a[maxn],basee[maxn] ;  
bool vis[maxn] ;

bool DFS(int u,int dad,int w){
    vis[u]=1 ; h[u]=h[dad]+1 ; 
    a[u]=w ;mol[u]=mol[dad] ;  
    for(auto i:adj[u]){
        if(i.ff!=dad){
            if(!vis[i.ff]){
                if(!DFS(i.ff,u,i.ss-a[u])) return 0  ;
            }
            else if(h[i.ff]%2!=h[u]%2){
                if(a[u]+a[i.ff]!=i.ss)  return 0 ;
            } 
            else if(basee[mol[u]]==INF){
                if(h[u]%2==1)   
                    basee[mol[u]]=(double)(i.ss-a[i.ff]-a[u])/2 ;
                else basee[mol[u]]=-1*(double)(i.ss-a[i.ff]-a[u])/2 ;
            }
            else{
                if((h[u]%2==1 ? 1:-1)*2*basee[mol[u]]+a[i.ff]+a[u]!=i.ss){  
                    return 0 ;
                }
            }
        }
    }
    return 1 ; 
}
void solve(){
    fill(basee , basee+maxn , INF) ; 
    for(int i=0 ; i<n ;i++)
        if(!vis[i]) {
            mol[i]=i ; if(!DFS(i,i,0)){ 
            cout<<"NO\n" ; return; }  }
            cout<<"YES\n" ; 
    for(int i=1 ; i<=n ; i++){
        cout<<fixed<<setprecision(7); 
        cout<<(double)a[i]+(basee[mol[i]]!=INF ? (h[i]%2==1?1:-1)*basee[mol[i]]:0)<<' ' ;
    } 
    
} 
int main(){
    ios::sync_with_stdio(0); cin.tie(0) ; 
    cin>>n>>m ;
    for(int i=0 ; i<m ;i++){
        int u,v,w ; cin>>u>>v>>w ; 
        adj[u].push_back({v,w}); 
        adj[v].push_back({u,w}); 
    }
    solve() ; 
}
#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...