| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 654884 |
2022-11-01T20:37:04 Z |
inksamurai |
Graph (BOI20_graph) |
C++17 |
|
1 ms |
212 KB |
#include <bits/stdc++.h>
// #define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3fm6nhZ ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
#define nare {cout<<"NO\n"; exit(0);}
using ld=long double;
const ld eps=1e-6;
signed main(){
_3fm6nhZ;
cout<<fixed<<setprecision(10);
int n,m;
cin>>n>>m;
vec(vec(pii)) adj(n);
map<pii,int> mp;
{
bool pok=1;
rep(_,m){
int u,v,w;
cin>>u>>v>>w;
u-=1,v-=1;
if(u>v) swap(u,v);
pii e=minmax(u,v);
if(mp.find(e)!=mp.end() and mp[e]!=w){
pok=0;
}
mp[e]=w;
adj[u].pb({w,v});
adj[v].pb({w,u});
}
if(!pok) nare;
}
vi usd2(n);
vec(ld) rbe(n);
vec(ld) rbts;
auto affine_=[&](int rt,ld x,int t=0)->ld{ // returns sum of values
vi way;
rbe[rt]=x;
auto rfs=[&](auto self,int v)->void{
way.pb(v);
usd2[v]=1;
for(auto e:adj[v]){
int u=e.se;
int w=e.fi;
if(usd2[u]) continue;
rbe[u]=(ld)(w)-rbe[v];
self(self,u);
}
};
rfs(rfs,rt);
ld res=0;
for(auto v:way){
for(auto e:adj[v]){
int u=e.se;
int w=e.fi;
if(u==v) continue;
// print(rbe[u],)
if(abs(w-rbe[u]-rbe[v])>eps) nare;
}
if(t) rbts.pb(rbe[v]);
res+=abs(rbe[v]);
usd2[v]=0;
}
return res;
};
auto slv=[&](int rt)->void{
ld l=-1e9,r=1e9;
rep(_,20){
ld ml=(2.0*l+r)/3.0;
ld mr=(l+2.0*r)/3.0;
if(affine_(rt,ml)<affine_(rt,mr)){
r=mr;
}else{
l=ml;
}
}
};
vec(vi) leb(n,vi(2));
vi usd1(n);
auto slvcyc=[&](int rt)->void{
// get way and cycle
vi way;
leb[rt][0]=1;
leb[rt][1]=0;
auto rfs=[&](auto self,int v)->void{
way.pb(v);
usd1[v]=1;
// print(v,leb[v][0],leb[v][1]);
for(auto e:adj[v]){
int u=e.se;
int w=e.fi;
if(usd1[u]) continue;
leb[u][0]=-leb[v][0];
leb[u][1]=w-leb[v][1];
self(self,u);
}
};
rfs(rfs,rt);
int nert=rt;
ld x;
bool pok=0;
for(auto v:way){
if(pok) break;
for(auto e:adj[v]){
int u=e.se;
int w=e.fi;
if(u==v){
pok=1;
x=(ld)(w)/2.0;
nert=v;
break;
}
vi now={-leb[v][0],w-leb[v][1]};
if(leb[u][0]!=now[0]){
x=(ld)(leb[u][1]-now[1])/(ld)(now[0]-leb[u][0]);
pok=1;
break;
}
}
}
if(!pok){
slv(nert);
}else{
// print("a",x,way[0]);
// print(x,way[0]);
affine_(nert,x);
}
};
bool cyc=0;
vi usd(n);
auto dfs=[&](auto self,int v,int par)->void{
usd[v]=1;
for(auto e:adj[v]){
int u=e.se;
if(u==par) continue;
if(usd[u]){
cyc=1;
}else{
self(self,u,v);
}
}
};
rep(rt,n){
if(usd[rt]) continue;
cyc=0;
dfs(dfs,rt,-1);
if(cyc){
slvcyc(rt);
}else{
slv(rt);
}
}
cout<<"YES\n";
rep(v,n)cout<<rbe[v]<<" ";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
answer = YES |
| 2 |
Incorrect |
0 ms |
212 KB |
participant answer is larger than the answer of jury |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
answer = YES |
| 2 |
Incorrect |
0 ms |
212 KB |
participant answer is larger than the answer of jury |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
answer = YES |
| 2 |
Incorrect |
0 ms |
212 KB |
participant answer is larger than the answer of jury |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
answer = YES |
| 2 |
Incorrect |
0 ms |
212 KB |
participant answer is larger than the answer of jury |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
answer = YES |
| 2 |
Incorrect |
0 ms |
212 KB |
participant answer is larger than the answer of jury |
| 3 |
Halted |
0 ms |
0 KB |
- |
