// #pragma GCC optimize("Ofast","unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
const long double epsilon = 1e-10;
struct constrains{
int k;
int vSign;
constrains():k(0),vSign(1){}
constrains(int a,int b):k(a),vSign(b){}
constrains(constrains &other, bool kind):k(1-other.k),vSign(-other.vSign){
if(kind)k++;
}
pair<bool,long double> equate(constrains other){
long double totVsign = vSign-other.vSign;
long double totK = other.k - k;
if(totVsign==0){
return {0,totK==0};
}
totK/=totVsign;
return {true,totK};
}
long double compute(long double x){
return k+vSign*x;
}
void add(constrains &other){
k+=other.k;
vSign+=other.vSign;
}
void subtract(constrains &other){
k-=other.k;
vSign-=other.vSign;
}
};
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N,M;
cin >> N >> M;
vector<vector<pair<int,bool>>> adj(N+1);
for(int i=1;i<=M;i++){
int u,v,c;
cin >> u >> v >> c;
adj[u].emplace_back(v,c==2);
adj[v].emplace_back(u,c==2);
}
vector<bool> visited(N+1);
vector<constrains> constrain(N+1);
vector<long double> answer(N+1);
bool works = true;
for(int i=1;i<=N;i++)if(!visited[i]){
vector<int> component;
bool rootvaldecided = false;
long double goodval = 0;
auto dfs = [&](auto&& self,int x,constrains c)->void{
if(visited[x]){
auto [type,rootval] = c.equate(constrain[x]);
if(type==0){
if(!rootval)works=false;
} else {
if(!rootvaldecided)goodval=rootval;
rootvaldecided=true;
if(abs(goodval-rootval)>epsilon)works=false;
}
return;
}
visited[x]=true;
constrain[x]=c;
component.emplace_back(x);
for(auto&[v,kind]:adj[x])self(self,v,{c,kind});
};
dfs(dfs,i,{});
if(!works)break;
if(!rootvaldecided){
// decide a good value
vector<pair<long double,constrains>> arr;
constrains sum(0,0);
for(int&j:component)if(constrain[j].vSign!=0){
auto c = constrain[j];
if(c.vSign<0){
c.vSign*=-1;
c.k*=-1;
}
auto [type,breakpoint] = c.equate({0,0});
assert(type);
arr.emplace_back(breakpoint,c);
sum.subtract(c);
}
pair<long double,long double> answer = {sum.compute(-1e10),-1e10};
for(auto&[point,c]:arr){
sum.add(c);
sum.add(c);
answer=min(answer,{sum.compute(point),point});
}
goodval=answer.second;
}
for(int&j:component)answer[j]=constrain[j].compute(goodval);
}
if(!works){
cout << "NO\n";
return 0;
}
cout << "YES\n";
for(int i=1;i<=N;i++){
cout << answer[i] << ' ';
}
cout << '\n';
}
# | 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... |