#include<bits/stdc++.h>
using namespace std;
const long long maxn=100000+10,lg=20;
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;
//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;
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 |
3 ms |
4948 KB |
answer = YES |
2 |
Correct |
3 ms |
4948 KB |
answer = YES |
3 |
Correct |
3 ms |
4948 KB |
answer = YES |
4 |
Correct |
3 ms |
4948 KB |
answer = NO |
5 |
Correct |
3 ms |
4948 KB |
answer = YES |
6 |
Correct |
3 ms |
4948 KB |
answer = YES |
7 |
Correct |
3 ms |
4948 KB |
answer = YES |
8 |
Correct |
2 ms |
4948 KB |
answer = YES |
9 |
Correct |
2 ms |
4948 KB |
answer = NO |
10 |
Correct |
2 ms |
4948 KB |
answer = YES |
11 |
Correct |
3 ms |
4948 KB |
answer = YES |
12 |
Correct |
2 ms |
4948 KB |
answer = NO |
13 |
Correct |
2 ms |
5012 KB |
answer = YES |
14 |
Correct |
2 ms |
4948 KB |
answer = YES |
15 |
Correct |
2 ms |
4948 KB |
answer = YES |
16 |
Correct |
3 ms |
4948 KB |
answer = YES |
17 |
Correct |
3 ms |
4948 KB |
answer = YES |
18 |
Correct |
2 ms |
4948 KB |
answer = YES |
19 |
Correct |
2 ms |
4948 KB |
answer = YES |
20 |
Correct |
2 ms |
4948 KB |
answer = YES |
21 |
Correct |
2 ms |
4948 KB |
answer = YES |
22 |
Correct |
2 ms |
4948 KB |
answer = NO |
23 |
Correct |
2 ms |
4948 KB |
answer = NO |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
answer = YES |
2 |
Correct |
3 ms |
4948 KB |
answer = YES |
3 |
Correct |
3 ms |
4948 KB |
answer = YES |
4 |
Correct |
3 ms |
4948 KB |
answer = NO |
5 |
Correct |
3 ms |
4948 KB |
answer = YES |
6 |
Correct |
3 ms |
4948 KB |
answer = YES |
7 |
Correct |
3 ms |
4948 KB |
answer = YES |
8 |
Correct |
2 ms |
4948 KB |
answer = YES |
9 |
Correct |
2 ms |
4948 KB |
answer = NO |
10 |
Correct |
2 ms |
4948 KB |
answer = YES |
11 |
Correct |
3 ms |
4948 KB |
answer = YES |
12 |
Correct |
2 ms |
4948 KB |
answer = NO |
13 |
Correct |
2 ms |
5012 KB |
answer = YES |
14 |
Correct |
2 ms |
4948 KB |
answer = YES |
15 |
Correct |
2 ms |
4948 KB |
answer = YES |
16 |
Correct |
3 ms |
4948 KB |
answer = YES |
17 |
Correct |
3 ms |
4948 KB |
answer = YES |
18 |
Correct |
2 ms |
4948 KB |
answer = YES |
19 |
Correct |
2 ms |
4948 KB |
answer = YES |
20 |
Correct |
2 ms |
4948 KB |
answer = YES |
21 |
Correct |
2 ms |
4948 KB |
answer = YES |
22 |
Correct |
2 ms |
4948 KB |
answer = NO |
23 |
Correct |
2 ms |
4948 KB |
answer = NO |
24 |
Correct |
3 ms |
4948 KB |
answer = YES |
25 |
Correct |
2 ms |
4948 KB |
answer = YES |
26 |
Correct |
2 ms |
4948 KB |
answer = YES |
27 |
Correct |
2 ms |
4948 KB |
answer = YES |
28 |
Correct |
2 ms |
4948 KB |
answer = YES |
29 |
Correct |
3 ms |
5024 KB |
answer = YES |
30 |
Correct |
3 ms |
4948 KB |
answer = NO |
31 |
Correct |
2 ms |
4948 KB |
answer = YES |
32 |
Correct |
2 ms |
4948 KB |
answer = YES |
33 |
Correct |
3 ms |
4948 KB |
answer = YES |
34 |
Correct |
2 ms |
4948 KB |
answer = YES |
35 |
Correct |
3 ms |
4948 KB |
answer = YES |
36 |
Correct |
2 ms |
4948 KB |
answer = YES |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
answer = YES |
2 |
Correct |
3 ms |
4948 KB |
answer = YES |
3 |
Correct |
3 ms |
4948 KB |
answer = YES |
4 |
Correct |
3 ms |
4948 KB |
answer = NO |
5 |
Correct |
3 ms |
4948 KB |
answer = YES |
6 |
Correct |
3 ms |
4948 KB |
answer = YES |
7 |
Correct |
3 ms |
4948 KB |
answer = YES |
8 |
Correct |
2 ms |
4948 KB |
answer = YES |
9 |
Correct |
2 ms |
4948 KB |
answer = NO |
10 |
Correct |
2 ms |
4948 KB |
answer = YES |
11 |
Correct |
3 ms |
4948 KB |
answer = YES |
12 |
Correct |
2 ms |
4948 KB |
answer = NO |
13 |
Correct |
2 ms |
5012 KB |
answer = YES |
14 |
Correct |
2 ms |
4948 KB |
answer = YES |
15 |
Correct |
2 ms |
4948 KB |
answer = YES |
16 |
Correct |
3 ms |
4948 KB |
answer = YES |
17 |
Correct |
3 ms |
4948 KB |
answer = YES |
18 |
Correct |
2 ms |
4948 KB |
answer = YES |
19 |
Correct |
2 ms |
4948 KB |
answer = YES |
20 |
Correct |
2 ms |
4948 KB |
answer = YES |
21 |
Correct |
2 ms |
4948 KB |
answer = YES |
22 |
Correct |
2 ms |
4948 KB |
answer = NO |
23 |
Correct |
2 ms |
4948 KB |
answer = NO |
24 |
Correct |
3 ms |
4948 KB |
answer = YES |
25 |
Correct |
2 ms |
4948 KB |
answer = YES |
26 |
Correct |
2 ms |
4948 KB |
answer = YES |
27 |
Correct |
2 ms |
4948 KB |
answer = YES |
28 |
Correct |
2 ms |
4948 KB |
answer = YES |
29 |
Correct |
3 ms |
5024 KB |
answer = YES |
30 |
Correct |
3 ms |
4948 KB |
answer = NO |
31 |
Correct |
2 ms |
4948 KB |
answer = YES |
32 |
Correct |
2 ms |
4948 KB |
answer = YES |
33 |
Correct |
3 ms |
4948 KB |
answer = YES |
34 |
Correct |
2 ms |
4948 KB |
answer = YES |
35 |
Correct |
3 ms |
4948 KB |
answer = YES |
36 |
Correct |
2 ms |
4948 KB |
answer = YES |
37 |
Correct |
3 ms |
5032 KB |
answer = YES |
38 |
Correct |
3 ms |
5076 KB |
answer = YES |
39 |
Correct |
4 ms |
5076 KB |
answer = YES |
40 |
Correct |
3 ms |
5204 KB |
answer = YES |
41 |
Correct |
4 ms |
5204 KB |
answer = NO |
42 |
Correct |
5 ms |
5204 KB |
answer = YES |
43 |
Correct |
4 ms |
5204 KB |
answer = YES |
44 |
Correct |
5 ms |
5156 KB |
answer = YES |
45 |
Correct |
6 ms |
5204 KB |
answer = YES |
46 |
Correct |
4 ms |
5092 KB |
answer = YES |
47 |
Correct |
4 ms |
5204 KB |
answer = YES |
48 |
Correct |
3 ms |
5204 KB |
answer = YES |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
answer = YES |
2 |
Correct |
3 ms |
4948 KB |
answer = YES |
3 |
Correct |
3 ms |
4948 KB |
answer = YES |
4 |
Correct |
3 ms |
4948 KB |
answer = NO |
5 |
Correct |
3 ms |
4948 KB |
answer = YES |
6 |
Correct |
3 ms |
4948 KB |
answer = YES |
7 |
Correct |
3 ms |
4948 KB |
answer = YES |
8 |
Correct |
2 ms |
4948 KB |
answer = YES |
9 |
Correct |
2 ms |
4948 KB |
answer = NO |
10 |
Correct |
2 ms |
4948 KB |
answer = YES |
11 |
Correct |
3 ms |
4948 KB |
answer = YES |
12 |
Correct |
2 ms |
4948 KB |
answer = NO |
13 |
Correct |
2 ms |
5012 KB |
answer = YES |
14 |
Correct |
2 ms |
4948 KB |
answer = YES |
15 |
Correct |
2 ms |
4948 KB |
answer = YES |
16 |
Correct |
3 ms |
4948 KB |
answer = YES |
17 |
Correct |
3 ms |
4948 KB |
answer = YES |
18 |
Correct |
2 ms |
4948 KB |
answer = YES |
19 |
Correct |
2 ms |
4948 KB |
answer = YES |
20 |
Correct |
2 ms |
4948 KB |
answer = YES |
21 |
Correct |
2 ms |
4948 KB |
answer = YES |
22 |
Correct |
2 ms |
4948 KB |
answer = NO |
23 |
Correct |
2 ms |
4948 KB |
answer = NO |
24 |
Correct |
3 ms |
4948 KB |
answer = YES |
25 |
Correct |
2 ms |
4948 KB |
answer = YES |
26 |
Correct |
2 ms |
4948 KB |
answer = YES |
27 |
Correct |
2 ms |
4948 KB |
answer = YES |
28 |
Correct |
2 ms |
4948 KB |
answer = YES |
29 |
Correct |
3 ms |
5024 KB |
answer = YES |
30 |
Correct |
3 ms |
4948 KB |
answer = NO |
31 |
Correct |
2 ms |
4948 KB |
answer = YES |
32 |
Correct |
2 ms |
4948 KB |
answer = YES |
33 |
Correct |
3 ms |
4948 KB |
answer = YES |
34 |
Correct |
2 ms |
4948 KB |
answer = YES |
35 |
Correct |
3 ms |
4948 KB |
answer = YES |
36 |
Correct |
2 ms |
4948 KB |
answer = YES |
37 |
Correct |
3 ms |
5032 KB |
answer = YES |
38 |
Correct |
3 ms |
5076 KB |
answer = YES |
39 |
Correct |
4 ms |
5076 KB |
answer = YES |
40 |
Correct |
3 ms |
5204 KB |
answer = YES |
41 |
Correct |
4 ms |
5204 KB |
answer = NO |
42 |
Correct |
5 ms |
5204 KB |
answer = YES |
43 |
Correct |
4 ms |
5204 KB |
answer = YES |
44 |
Correct |
5 ms |
5156 KB |
answer = YES |
45 |
Correct |
6 ms |
5204 KB |
answer = YES |
46 |
Correct |
4 ms |
5092 KB |
answer = YES |
47 |
Correct |
4 ms |
5204 KB |
answer = YES |
48 |
Correct |
3 ms |
5204 KB |
answer = YES |
49 |
Correct |
54 ms |
6624 KB |
answer = YES |
50 |
Correct |
9 ms |
7252 KB |
answer = YES |
51 |
Correct |
45 ms |
7252 KB |
answer = YES |
52 |
Correct |
9 ms |
7124 KB |
answer = NO |
53 |
Correct |
4 ms |
5156 KB |
answer = YES |
54 |
Correct |
9 ms |
5428 KB |
answer = YES |
55 |
Correct |
18 ms |
5844 KB |
answer = YES |
56 |
Correct |
45 ms |
6600 KB |
answer = YES |
57 |
Correct |
37 ms |
6388 KB |
answer = YES |
58 |
Correct |
30 ms |
6428 KB |
answer = YES |
59 |
Correct |
7 ms |
6356 KB |
answer = YES |
60 |
Correct |
28 ms |
6544 KB |
answer = YES |
61 |
Correct |
6 ms |
5888 KB |
answer = YES |
62 |
Correct |
45 ms |
15580 KB |
answer = NO |
63 |
Correct |
47 ms |
15604 KB |
answer = YES |
64 |
Correct |
52 ms |
15588 KB |
answer = NO |
65 |
Correct |
45 ms |
15620 KB |
answer = YES |
66 |
Correct |
6 ms |
5348 KB |
answer = YES |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
answer = YES |
2 |
Correct |
3 ms |
4948 KB |
answer = YES |
3 |
Correct |
3 ms |
4948 KB |
answer = YES |
4 |
Correct |
3 ms |
4948 KB |
answer = NO |
5 |
Correct |
3 ms |
4948 KB |
answer = YES |
6 |
Correct |
3 ms |
4948 KB |
answer = YES |
7 |
Correct |
3 ms |
4948 KB |
answer = YES |
8 |
Correct |
2 ms |
4948 KB |
answer = YES |
9 |
Correct |
2 ms |
4948 KB |
answer = NO |
10 |
Correct |
2 ms |
4948 KB |
answer = YES |
11 |
Correct |
3 ms |
4948 KB |
answer = YES |
12 |
Correct |
2 ms |
4948 KB |
answer = NO |
13 |
Correct |
2 ms |
5012 KB |
answer = YES |
14 |
Correct |
2 ms |
4948 KB |
answer = YES |
15 |
Correct |
2 ms |
4948 KB |
answer = YES |
16 |
Correct |
3 ms |
4948 KB |
answer = YES |
17 |
Correct |
3 ms |
4948 KB |
answer = YES |
18 |
Correct |
2 ms |
4948 KB |
answer = YES |
19 |
Correct |
2 ms |
4948 KB |
answer = YES |
20 |
Correct |
2 ms |
4948 KB |
answer = YES |
21 |
Correct |
2 ms |
4948 KB |
answer = YES |
22 |
Correct |
2 ms |
4948 KB |
answer = NO |
23 |
Correct |
2 ms |
4948 KB |
answer = NO |
24 |
Correct |
3 ms |
4948 KB |
answer = YES |
25 |
Correct |
2 ms |
4948 KB |
answer = YES |
26 |
Correct |
2 ms |
4948 KB |
answer = YES |
27 |
Correct |
2 ms |
4948 KB |
answer = YES |
28 |
Correct |
2 ms |
4948 KB |
answer = YES |
29 |
Correct |
3 ms |
5024 KB |
answer = YES |
30 |
Correct |
3 ms |
4948 KB |
answer = NO |
31 |
Correct |
2 ms |
4948 KB |
answer = YES |
32 |
Correct |
2 ms |
4948 KB |
answer = YES |
33 |
Correct |
3 ms |
4948 KB |
answer = YES |
34 |
Correct |
2 ms |
4948 KB |
answer = YES |
35 |
Correct |
3 ms |
4948 KB |
answer = YES |
36 |
Correct |
2 ms |
4948 KB |
answer = YES |
37 |
Correct |
3 ms |
5032 KB |
answer = YES |
38 |
Correct |
3 ms |
5076 KB |
answer = YES |
39 |
Correct |
4 ms |
5076 KB |
answer = YES |
40 |
Correct |
3 ms |
5204 KB |
answer = YES |
41 |
Correct |
4 ms |
5204 KB |
answer = NO |
42 |
Correct |
5 ms |
5204 KB |
answer = YES |
43 |
Correct |
4 ms |
5204 KB |
answer = YES |
44 |
Correct |
5 ms |
5156 KB |
answer = YES |
45 |
Correct |
6 ms |
5204 KB |
answer = YES |
46 |
Correct |
4 ms |
5092 KB |
answer = YES |
47 |
Correct |
4 ms |
5204 KB |
answer = YES |
48 |
Correct |
3 ms |
5204 KB |
answer = YES |
49 |
Correct |
54 ms |
6624 KB |
answer = YES |
50 |
Correct |
9 ms |
7252 KB |
answer = YES |
51 |
Correct |
45 ms |
7252 KB |
answer = YES |
52 |
Correct |
9 ms |
7124 KB |
answer = NO |
53 |
Correct |
4 ms |
5156 KB |
answer = YES |
54 |
Correct |
9 ms |
5428 KB |
answer = YES |
55 |
Correct |
18 ms |
5844 KB |
answer = YES |
56 |
Correct |
45 ms |
6600 KB |
answer = YES |
57 |
Correct |
37 ms |
6388 KB |
answer = YES |
58 |
Correct |
30 ms |
6428 KB |
answer = YES |
59 |
Correct |
7 ms |
6356 KB |
answer = YES |
60 |
Correct |
28 ms |
6544 KB |
answer = YES |
61 |
Correct |
6 ms |
5888 KB |
answer = YES |
62 |
Correct |
45 ms |
15580 KB |
answer = NO |
63 |
Correct |
47 ms |
15604 KB |
answer = YES |
64 |
Correct |
52 ms |
15588 KB |
answer = NO |
65 |
Correct |
45 ms |
15620 KB |
answer = YES |
66 |
Correct |
6 ms |
5348 KB |
answer = YES |
67 |
Correct |
244 ms |
32652 KB |
answer = YES |
68 |
Correct |
302 ms |
32536 KB |
answer = YES |
69 |
Correct |
60 ms |
32520 KB |
answer = YES |
70 |
Correct |
88 ms |
38864 KB |
answer = YES |
71 |
Correct |
58 ms |
32820 KB |
answer = YES |
72 |
Correct |
641 ms |
20984 KB |
answer = YES |
73 |
Correct |
78 ms |
21056 KB |
answer = YES |
74 |
Incorrect |
400 ms |
21088 KB |
jury has the better answer: jans = YES, pans = NO |
75 |
Halted |
0 ms |
0 KB |
- |