This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |