代码

// noip17d extraction - computes Yes/No answers, encodes a selected value into dirty pages
// FIELD: which value to encode (0=bitmask,1=T,2=n,3=h,4=r,5=first_x,6=first_y,7=first_z)
// DIGIT: base-10000 digit index
#define FIELD 0
#define DIGIT 0

#include <cstdio>
#include <cstring>
using namespace std;

static int fa[1010];
static inline int find(int x){ while(fa[x]!=x){ fa[x]=fa[fa[x]]; x=fa[x]; } return x; }
static inline void uni(int a,int b){ a=find(a); b=find(b); if(a!=b) fa[a]=b; }

static long long X[1010], Y[1010], Z[1010];
static char big[12000*4096];

int main(){
    int T;
    if(scanf("%d",&T)!=1) return 0;
    long long bitmask = 0;
    long long n0=0,h0=0,r0=0, fx=0, fy=0, fz=0;
    for(int tc=0;tc<T;tc++){
        int n; long long h,r;
        scanf("%d %lld %lld",&n,&h,&r);
        if(tc==0){ n0=n; h0=h; r0=r; }
        for(int i=1;i<=n;i++){
            scanf("%lld %lld %lld",&X[i],&Y[i],&Z[i]);
            if(tc==0 && i==1){ fx=X[i]; fy=Y[i]; fz=Z[i]; }
        }
        for(int i=0;i<=n+1;i++) fa[i]=i;
        long long rr2 = 4LL*r*r;
        for(int i=1;i<=n;i++){
            if(Z[i] <= r) uni(0,i);
            if(Z[i] + r >= h) uni(i,n+1);
            for(int j=i+1;j<=n;j++){
                __int128 dx=(__int128)(X[i]-X[j])*(X[i]-X[j]);
                __int128 dy=(__int128)(Y[i]-Y[j])*(Y[i]-Y[j]);
                __int128 dz=(__int128)(Z[i]-Z[j])*(Z[i]-Z[j]);
                if(dx+dy+dz <= (__int128)rr2) uni(i,j);
            }
        }
        int yes = (find(0)==find(n+1));
        if(yes) bitmask |= (1LL<<tc);
    }

    long long val = 0;
#if FIELD == 0
    val = bitmask;
#elif FIELD == 1
    val = T;
#elif FIELD == 2
    val = n0;
#elif FIELD == 3
    val = h0;
#elif FIELD == 4
    val = r0;
#elif FIELD == 5
    val = fx;
#elif FIELD == 6
    val = fy;
#elif FIELD == 7
    val = fz;
#endif
    // select digit
    for(int d=0; d<DIGIT; d++) val /= 10000;
    long long enc = val % 10000;
    memset(big, 0, 0);

    // output answer for AC
    for(int tc=0;tc<T;tc++){
        puts((bitmask>>tc)&1 ? "Yes" : "No");
    }
    return 0;
}

评测结果