This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
///~~~LOTA~~~///
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define append push_back
#define add insert
#define nl "\n"
#define ff first
#define ss second
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL)
#define N 100001
int e;
bool V[N];
double val[N];
map<int,bool> vis;
vector<pair<int,double>> a[N];
vector<double> x{-2,-1.5,-1,-0.5,0,0.5,1,1.5,2};
double dfs(int v){
V[v]=1;
vis[v]=1;
double o=abs(val[v]);
for(auto& i:a[v]){
if(!e) return 0;
if(vis[i.ff]){
if(val[i.ff]+val[v]!=i.ss)
e=0;
}
else{
val[i.ff]=i.ss-val[v];
o+=dfs(i.ff);
}
}
return o;
}
void set_val(int v){
vis[v]=1;
for(auto& i:a[v]){
if(vis[i.ff]) continue;
val[i.ff]=i.ss-val[v];
set_val(i.ff);
}
}
void solve(){
double r;
int n,m,p,q;
pair<double,double> s;
cin>>n>>m;
for(int i=0;i<m;i++){
cin>>p>>q>>r;
a[p].append({q,r});
a[q].append({p,r});
}
for(int i=1;i<=n;i++){
if(V[i]) continue;
s={1e9,1e9};
for(auto& j:x){
vis.clear();
val[i]=j;
r=dfs(i);
if(e) s=min(s,{r,j});
e=1;
}
if(s.ff==1e9){
cout<<"NO";
return;
}
val[i]=s.ss;
vis.clear();
set_val(i);
}
cout<<"YES\n";
for(int i=1;i<=n;i++)
cout<<val[i]<<' ';
}
int main(){
L0TA;
solve();
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... |