#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10;
vector<pair<long long,long long>>adj[maxn],adjt[maxn];
long long isr[maxn],vis[maxn],n,m,high[maxn],resf[maxn],resz[maxn],val[maxn];
long long res=1,timea=0;
vector<long long>now;
void dfs(long long u){
if(vis[u]==1){
return ;
}
now.push_back(u);
isr[u]=1;
vis[u]=1;
for(auto xx:adj[u]){
long long x=xx.first;
long long y=xx.second;
if(vis[x]==0){
adjt[u].push_back(xx);
adjt[x].push_back(make_pair(u,xx.second));
high[x]=high[u]+1;
if(high[u]&1){
resf[x]=resf[u];
resz[x]=resz[u]+y;
}
else{
resf[x]=resf[u]+y;
resz[x]=resz[u];
}
dfs(x);
}
}
}
pair<long long,long long> checkalle(){
for(auto x:now){
for(auto xx:adj[x]){
long long y=xx.first;
if(high[x]<high[y]){
continue;
}
if(high[x]==high[y]+1){
continue;
}
long long sf=resf[x]-resf[y],sz=resz[x]-resz[y];
if((high[x]&1)!=(high[y]&1)){
if(high[x]&1){
sz+=xx.second;
}
else{
sf+=xx.second;
}
if(sz==sf){
continue;
}
return make_pair(-2,-2);
}
if(high[x]&1){
sf+=xx.second;
}
else{
sz+=xx.second;
}
if(sz==sf){
continue;
}
long long ss;
if(high[x]&1){
ss=sf-sz;
}
else{
ss=sz-sf;
}
ss/=2;
//ss=-ss;
//cout<<x<<" "<<ss<<" "<<sz<<" "<<sf<<"wtf\n";
return make_pair(x,ss);
}
}
return make_pair(-1,-1);
}
long long por(long long u,long long w,long long par=0){
//cout<<u<<" "<<w<<" "<<par<<" asd\n";
val[u]=w;
long long ret=abs(w);
for(auto x:adjt[u]){
if(x.first!=par){
ret+=por(x.first,x.second-w,u);
}
}
return ret;
}
void solve(long long u){
now.clear();
dfs(u);
pair<long long,long long>fixy=checkalle();
if(fixy.first==-2){
res=0;
return ;
}
//cout<<u<<" "<<endl;
if(fixy.first!=-1){
por(fixy.first,fixy.second);
return ;
}
long long mina=1e17,w=0;
for(long long i=-150;i<150;i++){
long long z=por(u,i);
if(z<mina){
mina=z;
w=i;
}
else if(z==mina&&abs(i)<abs(w)){
w=i;
}
}
//cout<<por(u,0)<<" "<<por(u,2)<<" "<<mina<<" "<<w<<"\n";
por(u,w);
}
void checkakh(){
for(long long i=1;i<=n;i++){
for(auto x:adj[i]){
long long y=x.first;
//cout<<val[i]<<" "<<val[y]<<" "<<x.second<<"\n";
if(val[i]+val[y]!=x.second){
res=0;
assert(0);
return ;
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
//cout.tie(0);
cin>>n>>m;
for(long long i=0;i<m;i++){
long long u,v,w;
cin>>u>>v>>w;
w*=2;
adj[u].push_back(make_pair(v,w));
adj[v].push_back(make_pair(u,w));
}
for(long long i=1;i<=n;i++){
if(isr[i]==0){
//cout<<"ha: "<<i<<"\n";
solve(i);
}
}
////cout<<res<<"\n";
checkakh();
if(res==0){
cout<<"NO\n";
return 0;
}
cout<<"YES\n";
cout<<setprecision(2);
for(long long i=1;i<=n;i++){
if(val[i]<0){
cout<<"-";
}
val[i]=abs(val[i]);
if((val[i]&1)==1){
val[i]/=2;
cout<<val[i];
cout<<".5";
}
else{
val[i]/=2;
cout<<val[i];
}
cout<<" ";
}
cout<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
answer = YES |
| 2 |
Correct |
2 ms |
4948 KB |
answer = YES |
| 3 |
Correct |
4 ms |
5020 KB |
answer = YES |
| 4 |
Runtime error |
9 ms |
10068 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
answer = YES |
| 2 |
Correct |
2 ms |
4948 KB |
answer = YES |
| 3 |
Correct |
4 ms |
5020 KB |
answer = YES |
| 4 |
Runtime error |
9 ms |
10068 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
answer = YES |
| 2 |
Correct |
2 ms |
4948 KB |
answer = YES |
| 3 |
Correct |
4 ms |
5020 KB |
answer = YES |
| 4 |
Runtime error |
9 ms |
10068 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
answer = YES |
| 2 |
Correct |
2 ms |
4948 KB |
answer = YES |
| 3 |
Correct |
4 ms |
5020 KB |
answer = YES |
| 4 |
Runtime error |
9 ms |
10068 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
4948 KB |
answer = YES |
| 2 |
Correct |
2 ms |
4948 KB |
answer = YES |
| 3 |
Correct |
4 ms |
5020 KB |
answer = YES |
| 4 |
Runtime error |
9 ms |
10068 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
