Submission #1288610

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288610		hom84287	Graph (BOI20_graph)	C++17	0 / 100	2 ms	3396 KiB

Graph

#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() ; 
}

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