This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll maxn=1e5+10;
vector<pair<ll,ll> > g[maxn];
bool moze=true;
bool vis[maxn];
ll val[maxn];
ll sgn[maxn];
double res[maxn];
vector<int> comp;
set<ll> a;
void dfs(ll node){
comp.push_back(node);
vis[node]=true;
for(auto i:g[node]){
if(vis[i.first]){
if(sgn[i.first]!=sgn[node] && val[i.first]+val[node]!=i.second) moze=false;
if(sgn[i.first]==sgn[node]){
if(sgn[i.first]==1) a.emplace(i.second-val[node]-val[i.first]);
else a.emplace(val[i.first]+val[node]-i.second);
}
}else{
sgn[i.first]=-sgn[node];
val[i.first]=i.second-val[node];
dfs(i.first);
}
}
}
int main(){
ll n,m;
cin>>n>>m;
for(ll i=0;i<m;i++){
ll u,v,c;
cin>>u>>v>>c;
g[u].push_back({v,c});
g[v].push_back({u,c});
}
for(int i=1;i<=n;i++){
if(vis[i]) continue;
sgn[i]=1;
val[i]=0;
comp.clear();
a.clear();
dfs(i);
if(a.size()>1) moze=false;
if(a.size()==1){
double aa=*a.begin();
for(ll i:comp){
res[i]=aa*sgn[i]/2+val[i];
}
continue;
}
ll best=0;
ll curr=LLONG_MAX;
for(ll i:comp){
ll sum=0;
for(ll j:comp){
sum+=abs(val[j]+val[i]*sgn[i]*sgn[j]);
}
if(sum<curr){
curr=sum;
best=val[i];
}
}
for(ll i:comp){
res[i]=val[i]+best*sgn[i];
}
}
if(moze){
cout<<"YES\n";
cout<<fixed<<showpoint<<setprecision(15);
for(int i=1;i<=n;i++){
cout<<res[i];
cout<<" ";
}
}else cout<<"NO\n";
return 0;
}
# | 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... |