#include <iostream>
#include <vector>
#include <iomanip>
#include <map>
using namespace std;
#define ld long double
const int N = 2e5 + 10;
vector<vector<int>> nei[N];
int l[N],r[N],c[N];
ld a[N],b[N],inf = 1e9,ans[N];
int pen[100];
int seen[N];
map<pair<int,int>,int> mp;
int T = 1;
void dfs1(int u,int p = 0,int v = 0,int last = 0){
if (v >= 10){
last += pen[v];
if (a[u] != inf){
if (a[u] != last){
cout<<"NO\n";
exit(0);
}
return;
}
a[u] = last;
v = 0;
}
v *= 10;
for (auto i : nei[u]){
if (i[0] == p)
continue;
dfs1(i[0],u,v + i[1],last);
}
}
void dfs2(int u,int p = 0,int v = 0,int last = 0){
if (v >= 10){
last += pen[v];
if (b[u] != inf){
if (b[u] != last){
cout<<"NO\n";
exit(0);
}
return;
}
b[u] = last;
v = 0;
}
v *= 10;
for (auto i : nei[u]){
if (i[0] == p)
continue;
dfs2(i[0],u,v + i[1],last);
}
}
ld k;
void dfs3(int u){
for (auto i : nei[u]){
if (ans[i[0]] != inf)
continue;
ans[i[0]] = i[1] - ans[u];
dfs3(i[0]);
}
}
vector<int> vec,vv;
void get(int u){
seen[u] = true;
vv.push_back(u);
for (auto v : nei[u]){
if (seen[v[0]])
continue;
vec.push_back({v[2]});
get(v[0]);
}
}
ld calc(ld v){
ld ans = 0;
for (int i : vv){
if (a[i] != inf)
ans += abs(v + a[i]);
else
ans += abs(k - v + b[i]);
}
return ans;
}
signed main(){
cout<<fixed<<setprecision(9);
int n,m;
cin>>n>>m;
pen[21] = -1;
pen[12] = +1;
for (int i=1;i<=n;i++)
a[i] = b[i] = ans[i] = inf;
int cur = 1;
for (int i=1;i<=m;i++){
int u,v,t;
cin>>u>>v>>t;
if (mp[{u,v}] != 0){
if (mp[{u,v}] == t)
continue;
cout<<"NO"<<endl;
exit(0);
}
l[cur] = u;
r[cur] = v;
c[cur] = t;
cur++;
nei[u].push_back({v,t,i});
nei[v].push_back({u,t,i});
mp[{u,v}] = mp[{v,u}] = t;
}
m = cur - 1;
for (int i=1;i<=n;i++){
if (seen[i] or nei[i].size() == 0)
continue;
vec.clear();
vv.clear();
get(i);
bool con = false;
for (int j : vec)
if (l[j] == r[j]){
ans[l[j]] = c[j] / 2.0;
dfs3(l[j]);
con = true;
break;
}
if (con)
continue;
a[i] = 0;
dfs1(i);
int u = nei[i][0][0];
if (a[u] != inf){
ld A = nei[i][0][1] - a[u];
A = A / 2.0;
ans[i] = A;
dfs3(i);
continue;
}
dfs2(u);
k = nei[i][0][1];
ld lft = -1e5,rgt = nei[i][0][1];
while (rgt - lft > 0.00000001){
ld mid = (lft + rgt)/2.0;
ld frst = calc(mid);
ld sec = calc(mid + 0.00000001);
if (frst < sec)
rgt = mid;
else
lft = mid;
}
ans[i] = lft;
dfs3(i);
}
for (int i=1;i<=n;i++)
if (ans[i] == inf)
ans[i] = 0;
for (int i=1;i<=m;i++){
if (abs(c[i] - ans[l[i]] - ans[r[i]]) > 0.0000001){
cout<<"NO"<<endl;
return 0;
}
}
cout<<"YES"<<endl;
for (int i=1;i<=n;i++)
cout<<ans[i]<<" ";
cout<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
15196 KB |
answer = YES |
| 2 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 3 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 4 |
Correct |
3 ms |
15192 KB |
answer = NO |
| 5 |
Correct |
4 ms |
15196 KB |
answer = YES |
| 6 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 7 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 8 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 9 |
Correct |
2 ms |
15196 KB |
answer = NO |
| 10 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 11 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 12 |
Correct |
3 ms |
15196 KB |
answer = NO |
| 13 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 14 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 15 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 16 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 17 |
Correct |
2 ms |
11100 KB |
answer = YES |
| 18 |
Correct |
2 ms |
15196 KB |
answer = YES |
| 19 |
Incorrect |
3 ms |
15196 KB |
jury has the better answer: jans = YES, pans = NO |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
15196 KB |
answer = YES |
| 2 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 3 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 4 |
Correct |
3 ms |
15192 KB |
answer = NO |
| 5 |
Correct |
4 ms |
15196 KB |
answer = YES |
| 6 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 7 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 8 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 9 |
Correct |
2 ms |
15196 KB |
answer = NO |
| 10 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 11 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 12 |
Correct |
3 ms |
15196 KB |
answer = NO |
| 13 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 14 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 15 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 16 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 17 |
Correct |
2 ms |
11100 KB |
answer = YES |
| 18 |
Correct |
2 ms |
15196 KB |
answer = YES |
| 19 |
Incorrect |
3 ms |
15196 KB |
jury has the better answer: jans = YES, pans = NO |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
15196 KB |
answer = YES |
| 2 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 3 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 4 |
Correct |
3 ms |
15192 KB |
answer = NO |
| 5 |
Correct |
4 ms |
15196 KB |
answer = YES |
| 6 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 7 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 8 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 9 |
Correct |
2 ms |
15196 KB |
answer = NO |
| 10 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 11 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 12 |
Correct |
3 ms |
15196 KB |
answer = NO |
| 13 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 14 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 15 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 16 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 17 |
Correct |
2 ms |
11100 KB |
answer = YES |
| 18 |
Correct |
2 ms |
15196 KB |
answer = YES |
| 19 |
Incorrect |
3 ms |
15196 KB |
jury has the better answer: jans = YES, pans = NO |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
15196 KB |
answer = YES |
| 2 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 3 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 4 |
Correct |
3 ms |
15192 KB |
answer = NO |
| 5 |
Correct |
4 ms |
15196 KB |
answer = YES |
| 6 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 7 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 8 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 9 |
Correct |
2 ms |
15196 KB |
answer = NO |
| 10 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 11 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 12 |
Correct |
3 ms |
15196 KB |
answer = NO |
| 13 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 14 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 15 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 16 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 17 |
Correct |
2 ms |
11100 KB |
answer = YES |
| 18 |
Correct |
2 ms |
15196 KB |
answer = YES |
| 19 |
Incorrect |
3 ms |
15196 KB |
jury has the better answer: jans = YES, pans = NO |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
15196 KB |
answer = YES |
| 2 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 3 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 4 |
Correct |
3 ms |
15192 KB |
answer = NO |
| 5 |
Correct |
4 ms |
15196 KB |
answer = YES |
| 6 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 7 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 8 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 9 |
Correct |
2 ms |
15196 KB |
answer = NO |
| 10 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 11 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 12 |
Correct |
3 ms |
15196 KB |
answer = NO |
| 13 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 14 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 15 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 16 |
Correct |
3 ms |
15196 KB |
answer = YES |
| 17 |
Correct |
2 ms |
11100 KB |
answer = YES |
| 18 |
Correct |
2 ms |
15196 KB |
answer = YES |
| 19 |
Incorrect |
3 ms |
15196 KB |
jury has the better answer: jans = YES, pans = NO |
| 20 |
Halted |
0 ms |
0 KB |
- |
