记录编号	365056	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	2594.[Keller战纪·正传·妖姬篇][HZOI 2015]Keller非.a.t.e	最终得分	100
用户昵称	YGOI_真神名曰驴蛋蛋	是否通过	通过
代码语言	C++	运行时间	22.242 s
提交时间	2017-01-19 10:49:31	内存使用	10.03 MiB

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lson (root<<1)
#define rson (root<<1|1)
#define mid ((l+r)>>1)
typedef long long TYPE;
const TYPE MAXN=50010;
const TYPE MAXK=5;
struct NODE;
typedef std::pair<TYPE,NODE> pair;
TYPE rsqrt(const TYPE&x) {return x*x*x*x;}
inline int input() {
    static int c,k,t;k=0,t=1;
    do c=getchar(); while((c<'0' or c>'9')and c!='-');
    if(c=='-')t=-1,c=getchar();
    do k=k*10+c-'0',c=getchar(); while(c>='0' and  c<='9');
    return k*t;
}
TYPE idx,KD;
struct NODE {
    TYPE ele[MAXK];
    NODE() {memset(ele,0,sizeof ele);}
    bool operator <(const NODE&x) const{
        return ele[idx]<x.ele[idx];
    }
}IN[MAXN];
std::priority_queue<pair>que;
TYPE dist(const NODE&a,const NODE&b) {
    TYPE ans=0;
    for(TYPE i=0;i<KD;++i)
        ans+=rsqrt(a.ele[i]-b.ele[i]);
    return ans;
}
struct KD_TREE {
    KD_TREE() {memset(flag,0,sizeof flag);}
    void build(TYPE,TYPE,TYPE,TYPE);
    void query(NODE,TYPE,TYPE,TYPE);
    NODE data[MAXN<<2];
    bool flag[MAXN<<2];
}kid;
void KD_TREE::build(TYPE root,TYPE l,TYPE r,TYPE dept) {
    //printf("--->%lld %lld?\n",root,dept);
    if(l>r)return ;
    flag[root]=true;
    idx=dept%KD;
    std::nth_element(IN+l,IN+mid,IN+r+1);
    data[root]=IN[mid];
    build(lson,l,mid-1,dept+1);
    build(rson,mid+1,r,dept+1);
}
void KD_TREE::query(NODE p,TYPE kth,TYPE root,TYPE dept) {
    if(not flag[root])return ;
    pair cur(dist(data[root],p),data[root]);
    bool need=false;
    TYPE dim=dept%KD;
    TYPE x=lson,y=rson;
    if(p.ele[dim]>=data[root].ele[dim])
        std::swap(x,y);
    if(flag[x])query(p,kth,x,dept+1);
    if(que.size()<kth){que.push(cur);need=true;}
    else {
        if(cur.first<que.top().first) {que.pop();que.push(cur);}
        if(rsqrt(p.ele[dim]-data[root].ele[dim])<que.top().first)need=true;
    }
    if(flag[y] and need)query(p,kth,y,dept+1);
}
void print(NODE&data,NODE&p) {
    printf("%lld\n",dist(data,p));
}
bool Main() {
    TYPE N,M;KD=5;
    if(scanf("%lld%lld",&N,&M)!=2)
        return false;
    for(TYPE i=0;i<N;++i) {
        IN[i]=NODE();
        TYPE ds=input();
        for(TYPE j=0;j<ds;++j) {
            IN[i].ele[j]=input();
        }
    }kid.build(1,0,N-1,0);
    for(TYPE T=0;T<M;++T) {
        NODE p;TYPE kth,vs;
        while(!que.empty())que.pop();
        vs=input();kth=input();
        for(TYPE j=0;j<vs;++j) 
            p.ele[j]=input();
        kid.query(p,kth,1,0);
        printf("the closest %d strings' distance are:\n",que.size());
        NODE c[25];
        for(TYPE i=0;!que.empty();++i) {
            c[i]=que.top().second;que.pop();
        }for(TYPE i=kth-1;i>=0;--i) {
            print(c[i],p);
        }
    }
    return true;
}
int main() {
    freopen("Keller_Deal.in","r",stdin);
    freopen("Keller_Deal.out","w",stdout);
    while(Main());
    fclose(stdin);fclose(stdout);
    return 0;
}