如果把这个代码用 CF 上的 c++14 交上去会 WA Test 4,输出 -1
。如果用 c++17 Diagnosis 发现 Test 4 是能过的。最后发现是浮点数误差问题以后就过了 Accepted。
但是问题就来了,一开始第一个代码在 Test 4 输出 -1,我把第一个代码中开头的结构体函数
inline double operator * (const node aa)const{
double pos=0;
if(aa.k==k) pos=(aa.b==b)?max(s,aa.s):1e18;
else pos=1.*(aa.b-b)/(k-aa.k);
return (inr(pos)&&aa.inr(pos))?pos:1e18;
}
里面加了一行调试语句,其实输出任何东西都行,printf, cout, cerr, puts 之类都行,加进去,放到 CF custom innovation 里面测一下,最后一行输出的都是正确结果。请问是不是开了 O2 优化以后 double 发生了什么奇怪的问题?
修改以后变成:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
double c[N*2],now,ans=1e18;
struct node{
double s,t,k,b;
inline double cal(double x)const{ return k*x+b;}
inline double inr(double x)const{ return x>=s&&x<=t;}
inline bool operator < (const node aa)const{ return cal(now)<aa.cal(now);}
inline bool operator == (const node aa)const{ return cal(now)==aa.cal(now);}
inline double operator * (const node aa)const{
double pos=0;
if(aa.k==k) pos=((aa.b==b)?max(s,aa.s):1e18);
else pos=1.*(aa.b-b)/(k-aa.k);
puts("gg");
return (pos>=s&&pos<=t&&pos>=aa.s&&pos>=aa.t)?pos:1e18;
}
};
multiset<node> s;
vector<node> vec1[N*2],vec2[N*2];
void solve(vector<node> vec){
int top=0; s.clear();
for(auto &z:vec)
z.b-=z.k*z.s,c[++top]=z.s,c[++top]=z.t;
sort(c+1,c+top+1);
int tg=top; top=0; c[0]=-1e9;
for(int i=1;i<=tg;++i)
if(c[i]-c[i-1]>1e-8) c[++top]=c[i];
for(int i=top+1;i<=tg;++i) c[i]=-1e9;
for(int i=1;i<=top;++i)
vec1[i].clear(),vec2[i].clear();
for(auto z:vec){
int ps=lower_bound(c+1,c+top+1,z.s)-c;
int pt=lower_bound(c+1,c+top+1,z.t)-c;
if(fabs(z.s-c[ps])>fabs(z.s-c[ps-1])) --ps;
if(fabs(z.t-c[pt])>fabs(z.t-c[pt-1])) --pt;
vec1[ps].emplace_back(z);
vec2[pt].emplace_back(z);
}
for(int i=1;i<=top&&c[i]<ans;++i){
now=c[i];
for(auto z:vec1[i]){
s.insert(z);
auto it=s.find(z),is=it;
if(it!=s.begin()) is=it,--is,ans=min(ans,(*is)*(*it)); is=it;
if((++is)!=s.end()) ans=min(ans,(*is)*(*it));
}
for(auto z:vec2[i]){
auto it=s.find(z),is=it,ir=it;
++ir;
if(ir!=s.end()&&it!=s.begin()) --is,ans=min(ans,(*is)*(*ir));
s.erase(it);
}
}
}
int n,m,son[N],sz[N],dfn[N],dfncl,d[N],f[N],top[N];
vector<int> e[N];
vector<node> vc[N];
void dfs1(int u,int fa){
f[u]=fa,sz[u]=1;
for(int v:e[u]){
if(v==fa) continue;
dfs1(v,u),sz[u]+=sz[v];
if(sz[v]>sz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int fa,int tp){
dfn[u]=++dfncl,top[u]=tp,d[u]=d[fa]+1;
if(son[u]) dfs2(son[u],u,tp);
for(int v:e[u])
if(v!=fa&&v!=son[u]) dfs2(v,u,v);
}
int dist(int u,int v){
int res=0;
for(;top[u]!=top[v];res+=d[u]-d[top[u]]+1,u=f[top[u]])
if(d[top[u]]<d[top[v]]) swap(u,v);
return res+abs(d[u]-d[v]);
}
void add(int v,int u,double s,int c){
double t=s+1.*dist(u,v)/c;
for(;top[u]!=top[v];)
if(d[top[u]]>d[top[v]]){
vc[top[u]].emplace_back(
(node){t-1.*(d[u]-d[top[u]]+1)/c,t,1.*c,1.*(d[top[u]]-1)});
t-=1.*(d[u]-d[top[u]]+1)/c,u=f[top[u]];
}
else{
vc[top[v]].emplace_back(
(node){s,s+1.*(d[v]-d[top[v]]+1)/c,-1.*c,1.*d[v]});
s+=1.*(d[v]-d[top[v]]+1)/c,v=f[top[v]];
}
vc[top[u]].emplace_back(
(node){s,t,1.*(d[v]>d[u]?-c:c),1.*d[v]});
}
int main(){
cin>>n>>m;
for(int i=1,u,v;i<n;++i){
scanf("%d%d",&u,&v);
e[u].emplace_back(v);
e[v].emplace_back(u);
}
dfs1(1,0),dfs2(1,0,1);
for(int i=1,t,c,v,u;i<=m;++i)
scanf("%d%d%d%d",&t,&c,&v,&u),add(v,u,t,c);
for(int i=1;i<=n;++i)
if(vc[i].size()) solve(vc[i]);
if(ans>2e4) puts("-1");
else printf("%.10lf",ans);
return 0;
}
但在第一个代码本地和洛谷 IDE 上、CF C++17 Diagnosis 上输出都是对的,所以是不是 CF 的 C++14 有问题啊?