#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
#define ld long double
vector<pair<int,int>> ma[N];
int h[N],pre[N];
bool vis[N];
vector<pair<int,ld>> pos;
set<int> anc;
double val[N],sum[N],fin[N];
bool flip[N],posa[N];
void dfs(int x,int p=-1)
{
vis[x]=1;
cout<<"Parent "<<p<<' '<<x<<endl;
if(p==-1)
{
h[x]=0;
}
else{
h[x]=(h[p]+1)%2;
}
vis[x]=1;
anc.insert(x);
for(auto [y,w]:ma[x])
{
if(y!=p)
{
if(vis[y] and anc.find(y)!=anc.end())
{
// Cylce
// WE
// a[1]->a[2]->a[3]->a[4]
//a[1]+a[2]==pre[2]
// a[1]+a[2]+a[2]+a[3]=pre[3]
// a[1]+a[2]+a[2]+a[3]+a[3]+a[4]=pre[4]
// a[3]+a[4]=w
// pre[4]-w
cout<<"Hola Cycle "<<x<<' '<<y<<endl;
if((h[y]==h[x]))
{
if(h[x]==1)
{
ld p=pre[y]-pre[x];
ld q=w;
pos.push_back({y,(p+q)/2.0});
}
else{
ld p=pre[x];
ld q=w;
pos.push_back({y,(p+q)/2.0});
}
}
}
else{
if(h[x]==0)
{
pre[y]=pre[x]+w;
}
else{
pre[y]=pre[x]-w;
}
dfs(y,x);
}
}
}
anc.erase(x);
}
set<int> visp;
bool check(int x,double vl)
{
// cout<<"For vertex "<<x<<" then it is "<<vl<<endl;
// visp.insert(x);
vis[x]=1;
flip[x]=1;
val[x]=vl;
for(auto [y,w]:ma[x])
{
// if(visp.find(y)==visp.end())
if(!vis[y])
{
flip[x]&=check(y,w-vl);
}
else if((val[y])!=(w-val[x]))
{
flip[x]=0;
}
else
{
flip[x]&=flip[y];
}
}
return flip[x];
}
int part[N];
void init(int n)
{
for(int i=1;i<=n;i++)
part[i]=i;
}
int root(int x)
{
return ((part[x]==x)?x:part[x]=root(part[x]));
}
void join(int x,int y)
{
x=root(x);
y=root(y);
if(x!=y)
{
part[x]=y;
}
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
sum[i]=1e9;
}
init(n);
for(int j=0;j<m;j++)
{
int a,b,c;
cin>>a>>b>>c;
join(a,b);
ma[a].push_back({b,c});
ma[b].push_back({a,c});
}
for(int i=1;i<=n;i++)
{
if(!posa[root(i)])
{
for(double vl=-3;vl<=3;vl+=0.5)
{
for(int i=1;i<=n;i++){
vis[i]=0;
}
if(check(i,vl))
{
// cout<<"Can place values\n";
double dp=0;
for(auto j:visp)
dp+=abs(val[j]);
// cout<<"Done sum = "<<dp<<endl;
if(dp<sum[root(i)])
{
posa[root(i)]=1;
for(auto j:visp)
fin[j]=val[j];
sum[root(i)]=dp;
}
}
}
}
}
bool pos=1;
for(int i=1;i<=n;i++)
{
pos&=(posa[root(i)]);
}
if(pos)
{
cout<<"YES\n";
for(int i=1;i<=n;i++)
{
cout<<fin[i]<<' ';
}
cout<<'\n';
}
else{
cout<<"NO\n";
}
return 0;
}
/*
a[4]+a[1]
a[1]+a[2]
a[2]+a[3]
a[4]+a[3]
// a[3]-a[1]
// a[1]-a[3] == p
// a[1]+a[3] == q
// a[1] == (p+q)/2
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Sum of endpoints for edge (1; 2) differs from the expected value 1. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Sum of endpoints for edge (1; 2) differs from the expected value 1. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Sum of endpoints for edge (1; 2) differs from the expected value 1. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Sum of endpoints for edge (1; 2) differs from the expected value 1. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Sum of endpoints for edge (1; 2) differs from the expected value 1. |
| 2 |
Halted |
0 ms |
0 KB |
- |
