bzoj:3616: War

时间：2023-03-08 17:40:12
bzoj:3616: War

Description

小x所在的世界正在经历一场在k个阵营之间的战争。每个阵营有若干个炮塔，每个炮塔由攻击系统和防御系统组成。第i个炮塔可以攻击到离它欧几里德距离小于等于ri 或者曼哈顿距离小于等于ai的炮塔，被攻击到的炮塔防御系统就会崩溃，同一联盟的炮塔不会被攻击到。每次会随机选择一个炮塔攻击它能打到的所有炮塔，问进行m轮后期望剩下多少个阵营，使得这些阵营拥有的炮塔的防御系统全部完好。防御系统崩溃的炮塔还是会被打到的。值得注意的是，如果一个联盟没有任何炮塔，那么不管怎样它都是完好的。

Input

　　输入文件第一行有三个整数n、m、k，分别表示炮塔数目、攻击轮数以及联盟个数。 接下去n行每行有五个正整数xi、yi、ri、ai、pi，其中xi、yi表示炮塔坐标，p表示炮塔所属于阵营。

Output

　　输出一行一个实数表示答案，你的输出与标准输出的误差在1e-3以内会被认为是正确的。

Sample Input

2 2 3
0 0 2 2 1
1 1 2 2 2

Sample Output

1.500
建完k-d树直接查找记得打标记就好了。
然而某邻接表写炸，RE了两发，最后#8还是不错的
从网上拷来3份标程（CA，Claris，鸟神），加上自己的AC代码共4份，随机造数据居然能出现4个不同的答案……（CA爷的代码最不和群
#include<cmath>

#include<bitset>

#include<cstdio>

#include<vector>

#include<algorithm>

#define ii inline int

#define MN 36000

#define MM 5000000

using namespace std;

int n,m,f,ro=,num=,xx,X,o,la=,NO,l[MN+],k;

double MMH=;

char cs;

ii read(){

    cs=getchar();xx=;f=;

    while(cs<''||cs>'') {if (cs=='-') f=-;cs=getchar();}

    while(cs>=''&&cs<='') xx=xx*+cs-,cs=getchar();

    return xx*f;

}

struct tr{

    int x,y,r,a;

    friend bool operator<(tr a,tr b){if (X) return a.y<b.y;else return a.x<b.x;}

    friend bool operator ==(tr a,tr b){return (a.x==b.x)&&(a.y==b.y);}

}a[MN+],aw;

struct tree{

    int xa,xi,ya,yi,l,r;

}t[MN+];

struct na{

    int y,ne;

}b[MM];

inline void in(int x,int y){

    b[++num].y=y;b[num].ne=l[x];l[x]=num;

}

bitset<MN+> G[MN+];

vector <int> V[MN+];

ii S(int x){return x*x;}

ii A(int a,int b){return a>b?a:b;}

ii I(int a,int b){return a<b?a:b;}

ii B(int a){return a<?-a:a;}

ii build(int l,int r,int now){

    X=now;

    int mid=(l+r)>>;

    nth_element(a+l,a+mid,a+r+);

    t[mid].xa=t[mid].xi=a[mid].x;

    t[mid].ya=t[mid].yi=a[mid].y;

    t[mid].l=t[mid].r=;

    if (l<mid) t[mid].l=build(l,mid-,now^),

    t[mid].xa=A(t[t[mid].l].xa,t[mid].xa),

    t[mid].xi=I(t[t[mid].l].xi,t[mid].xi),

    t[mid].ya=A(t[t[mid].l].ya,t[mid].ya),

    t[mid].yi=I(t[t[mid].l].yi,t[mid].yi);

    if (mid<r) t[mid].r=build(mid+,r,now^),

    t[mid].xa=A(t[t[mid].r].xa,t[mid].xa),

    t[mid].xi=I(t[t[mid].r].xi,t[mid].xi),

    t[mid].ya=A(t[t[mid].r].ya,t[mid].ya),

    t[mid].yi=I(t[t[mid].r].yi,t[mid].yi);

    return mid;

}

ii gnm(int j){return A(a[NO].x-t[j].xa,)+A(t[j].xi-a[NO].x,)+A(a[NO].y-t[j].ya,)+A(t[j].yi-a[NO].y,);}

ii gnq(int j){return S(A(a[NO].x-t[j].xa,)+A(t[j].xi-a[NO].x,))+S(A(a[NO].y-t[j].ya,)+A(t[j].yi-a[NO].y,));}

ii gmm(int j){return A(B(a[NO].x-t[j].xa),B(a[NO].x-t[j].xi))+A(B(a[NO].y-t[j].yi),B(a[NO].y-t[j].ya));}

ii gmq(int j){return S(A(B(a[NO].x-t[j].xa),B(a[NO].x-t[j].xi)))+S(A(B(a[NO].y-t[j].yi),B(a[NO].y-t[j].ya)));}

ii in(int x){

    if (gmq(x)<=a[NO].r) return ;

    if (gmm(x)<=a[NO].a) return ;

    if (gnq(x)<=a[NO].r) return ;

    if (gnm(x)<=a[NO].a) return ;

    return ;

}

ii ju(int x){

    if (S(a[x].x-a[NO].x)+S(a[x].y-a[NO].y)<=a[NO].r) return ;

    if (B(a[x].x-a[NO].x)+B(a[x].y-a[NO].y)<=a[NO].a) return ;

    return ;

}

ii que(int p){

    int u=in(p);

    if (u)

    if (u==) G[p][NO]=;else{

        if (ju(p)) in(p,NO);

        if (t[p].l) que(t[p].l);

        if (t[p].r) que(t[p].r);

    }

}

inline void dw(int p){

    if (t[p].l) G[t[p].l]|=G[p],dw(t[p].l);

    if (t[p].r) G[t[p].r]|=G[p],dw(t[p].r);

    for (register int i=l[p];i;i=b[i].ne) G[p][b[i].y]=;

}

int main(){

    register int i,j;

    n=read();m=read();k=read();

    for (i=;i<=n;i++) a[i].x=read(),a[i].y=read(),a[i].r=S(read()),a[i].a=read(),V[read()].push_back(i);

    ro=build(,n,);

    for (NO=;NO<=n;NO++) que(ro);

    dw(ro);

    for (i=;i<=k;i++){

        G[]=;

        for (j=;j<V[i].size();j++) G[]|=G[V[i][j]];

        for (j=;j<V[i].size();j++) G[][V[i][j]]=;

        MMH+=pow(1.0-(1.0*G[].count()/n),m);

    }

    printf("%.6lf\n",MMH);

}

200724 kb 8588 ms C++/Edit 3446 B

相关文章