#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10;
vector<pair<int,int>>adj[maxn],adjt[maxn];
int isr[maxn],vis[maxn],n,m,high[maxn],resf[maxn],resz[maxn],val[maxn];
int res=1,timea=0;
vector<int>now;
void dfs(int u){
if(vis[u]==1){
return ;
}
now.push_back(u);
isr[u]=1;
vis[u]=1;
for(auto xx:adj[u]){
int x=xx.first;
int 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<int,int> checkalle(){
for(auto x:now){
for(auto xx:adj[x]){
int y=xx.first;
if(high[x]<high[y]){
continue;
}
if(high[x]==high[y]+1){
continue;
}
int 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){
return make_pair(x,0);
continue;
}
int 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);
}
int por(int u,int w,int par=0){
//cout<<u<<" "<<w<<" "<<par<<" asd\n";
val[u]=w;
int ret=abs(w);
for(auto x:adjt[u]){
if(x.first!=par){
ret+=por(x.first,x.second-w,u);
}
}
return ret;
}
void solve(int u){
now.clear();
dfs(u);
pair<int,int>fixy=checkalle();
if(fixy.first==-2){
res=0;
return ;
}
//cout<<u<<" "<<endl;
if(fixy.first!=-1){
por(fixy.first,fixy.second);
return ;
}
int low=-1000,high=1000,w,mid;
while(high-low>1){
int mid=(high+low)>>1;
long long av=por(u,mid),dov=por(u,mid+1);
if(av<=dov){
low=mid;
}
else{
high=mid;
}
}
if(por(u,low)>por(u,high)){
w=low;
}
else{
w=high;
}
//cout<<por(u,0)<<" "<<por(u,2)<<" "<<mina<<" "<<w<<"\n";
por(u,w);
}
void checkakh(){
for(int i=1;i<=n;i++){
for(auto x:adj[i]){
int y=x.first;
//cout<<val[i]<<" "<<val[y]<<" "<<x.second<<"\n";
if(val[i]+val[y]!=x.second){
res=0;
return ;
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
//cout.tie(0);
cin>>n>>m;
for(int i=0;i<m;i++){
int 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(int 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(int 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";
}
Compilation message
Graph.cpp: In function 'void solve(int)':
Graph.cpp:110:28: warning: unused variable 'mid' [-Wunused-variable]
110 | int low=-1000,high=1000,w,mid;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
answer = YES |
| 2 |
Incorrect |
2 ms |
4948 KB |
participant answer is larger than the answer of jury |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
answer = YES |
| 2 |
Incorrect |
2 ms |
4948 KB |
participant answer is larger than the answer of jury |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
answer = YES |
| 2 |
Incorrect |
2 ms |
4948 KB |
participant answer is larger than the answer of jury |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
answer = YES |
| 2 |
Incorrect |
2 ms |
4948 KB |
participant answer is larger than the answer of jury |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
answer = YES |
| 2 |
Incorrect |
2 ms |
4948 KB |
participant answer is larger than the answer of jury |
| 3 |
Halted |
0 ms |
0 KB |
- |
