#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<int,pii>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
vector<pii>adj[100005];
bool visited[100005];
vector<int>storage[2];
pii arr[100005];
bool amos=true;
vector<int>need;
void dfs(int index, int val, int sgn){
arr[index]={val,sgn};
storage[sgn].push_back(val);
//show3(index,index,val,val,sgn,sgn);
visited[index]=true;
for(auto it:adj[index]){
int nval=it.second-val;
int nsgn=1-sgn;
if(visited[it.first]){
if(arr[it.first].second==nsgn&&arr[it.first].first!=nval) amos=false;
if(arr[it.first].second!=nsgn){
int a=arr[it.first].first;
int b=nval;
if(nsgn) swap(a,b); //b is the k-x
need.push_back(b-a);
}
}
if(!visited[it.first]){
dfs(it.first,nval,nsgn);
}
}
}
void solve(){
int n,m;
cin >> n >> m;
int temp,temp2,temp3;
for(int x=0;x<m;x++){
cin >> temp >> temp2 >> temp3;
adj[temp].push_back({temp2,temp3});
adj[temp2].push_back({temp,temp3});
}
dfs(1,0,1);
//show(amos,amos);
int counter=0;
while(!storage[0].empty()&&!storage[1].empty()){
counter+=storage[0].back();
counter+=storage[1].back();
storage[0].pop_back();
storage[1].pop_back();
}
ld hold=0;
if(!storage[0].empty()){
//k-x
sort(storage[0].begin(),storage[0].end());
hold=storage[0][storage[0].size()/2];
}
if(!storage[1].empty()){
//k+x
sort(storage[1].begin(),storage[1].end());
hold=-storage[1][storage[1].size()/2];
}
//show4(need,need);
//sort(need.begin(),need.end());
need.resize(unique(need.begin(),need.end())-need.begin());
if(!amos||need.size()>1){
cout << "NO\n";
}
else{
if(!need.empty()) hold=(ld)need[0]/2;
cout << "YES\n";
for(int x=1;x<=n;x++){
ld cur=arr[x].first;
if(arr[x].second==1) cur-=hold;
else cur+=hold;
cout << fixed << setprecision(10) << cur << " ";
}
}
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int t=1;
//cin >> t;
while(t--){
solve();
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |