竞赛讨论区 > 求助T4,大样例没过,40pts,后六个点WA
头像
LaurieQi
发布于 2020-10-27 22:12
+ 关注

求助T4,大样例没过,40pts,后六个点WA

RT

//#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#include 
//#include 
#define itn int
#define nit int
#define ll long long
#define ms multiset
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
#define openf(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout)
#define re register
#define ri re int
#define x first
#define y second
#define il inline
#define cp complex
#define pii pair
//#pra gma G CC opti mize(3)
using namespace std;
using std::bitset;
//using namespace __gnu_pbds;
const double Pi=acos(-1);
inline int read() {
    int x=0;
    bool fu=0;
    char ch=0;
    while(ch>'9'||ch<'0') {
        ch=getchar();
        if(ch=='-')fu=1;
    }
    while(ch='0') x=(x*10-48+ch),ch=getchar();
    return fu?-x:x;
}
int n,f[100002],dp[100002],fa[100002][22],q,t1,t2,t3;
long double r[100002],now,eps=1e-9;
pii ct[100002];
vectorc[100002];
struct node{
    int pos;
    bool tp;
    inline double getx(){
        if(tp)return sqrt(max(0.0l,r[pos]*r[pos]-(now-ct[pos].y)*(now-ct[pos].y)))+ct[pos].x+eps;
        else return -sqrt(max(0.0l,r[pos]*r[pos]-(now-ct[pos].y)*(now-ct[pos].y)))+ct[pos].x-eps;
    }friend bool operator<(node a,node b){
        return a.getx()<b.getx();
    }
}temp;
pairadd[100002],mns[100002];
inline bool cmp(paira,pairb){
    return a.first<b.first;
}inline void dfs(int pos){
    dp[pos]=dp[f[pos]]+1;
    fa[pos][0]=f[pos];
    F(i,1,20)fa[pos][i]=fa[fa[pos][i-1]][i-1];
    F(i,0,c[pos].size()-1)dfs(c[pos][i]);
}inline int lca(int x,int y){
    while(dp[x]>dp[y]){
        UF(i,20,0){
            if(dp[fa[x][i]]>=dp[y])x=fa[x][i];
        }
    }while(dp[x]<dp[y]){
        UF(i,20,0){
            if(dp[fa[y][i]]>=dp[x])y=fa[y][i];
        }
    }if(x==y)return x;
    UF(i,20,0){
        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
    }return f[x];
}
sets;
int main(){freopen("D.in","r",stdin);
    ct[0]=make_pair(0.0,0.0);
    r[0]=LLONG_MAX;
    cin>>n;
    F(i,1,n){
        ct[i]=make_pair((double)read(),(double)read());
        r[i]=read();
        add[i]=make_pair(ct[i].second-r[i],i);
        mns[i]=make_pair(ct[i].second+r[i],i);
    }sort(add+1,add+n+1,cmp),sort(mns+1,mns+n+1,cmp);
    int i=1,j=1;
    add[n+1].first=INT_MAX;
    mns[n+1].first=INT_MAX;
    s.insert((node){0,0});
    s.insert((node){0,1});
    F(iakioi,1,n+n){//cout<<s.size()<<endl;
        if(add[i].first<=mns[j].first){
            now=add[i].first;
            s.insert((node){add[i].second,0});
            s.insert((node){add[i].second,1});
            temp=*s.upper_bound((node){add[i].second,1});
            if(temp.tp){
                f[add[i].second]=temp.pos;
                c[temp.pos].push_back(add[i].second);
            }else{/*cout<<f[temp.pos]<<' '<<add[i].second<<endl;*/
                f[add[i].second]=f[temp.pos];
                c[f[temp.pos]].push_back(add[i].second);
            }i++;
        }else{
            now=mns[j].first;
            s.erase((node){mns[j].second,0});
            s.erase((node){mns[j].second,1});
            j++;
        }
    }dfs(0);
    cin>>q;
    while(q--){
        t1=read(),t2=read();
        if(t1==t2){
            printf("0\n");
            continue;
        }
        t3=lca(t1,t2);
        if(t3==t1||t3==t2){
            printf("%d\n",int(abs(dp[t1]-dp[t2])-1));
            continue;
        }printf("%d\n",dp[t1]-dp[t3]+dp[t2]-dp[t3]-2);
    }/*F(i,1,n)cout<<f[i]<<' ';*/
    return 0;
}

全部评论

(2) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐