题解：P10097 [ROIR 2023 Day 1] 彩点

· · 题解

考虑转化成图论问题。

我们从 (i,j) 到 (j,k) 连一条边当且仅当从起始点 i，终止点 j 的状态可以转化成起始点 j，终止点 k 的状态。先考虑如何建图，考虑枚举终止点 j，然后将其余点按与 j 点连边后与 x 轴正方向的夹角排序，这里可以先按所在象限排序，再按斜率排序。然后我们考虑枚举 i，那么可以直接二分出来对应的 k，这样就能在 \mathcal O(n^2\log n) 的时间内完成建图。

那么建完图之后，一个点 i 如果是绿色点当且仅当存在 j 使得 (i,j) 在一个环内，一个点 i 如果是蓝色点当且仅当它不是绿色点并且存在 j\neq k 使得 (i,j) 可以到达 (i,k)。

考虑缩点，第一问是简单的，第二问直接对于每个点维护一个 bitset，第 i 位表示这个点是否有 j 使得这个点能到达 (i,j) 就可以了。

时间复杂度 \mathcal O(n^2\log n+\frac{n^3}{\omega})。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,t,m,x[1005],y[1005],low[1000005],dfn[1000005],st[1000005],top,ins[1000005],cntt,fr[1000005],cnt,vis[1005],fff[1005],co[1000005],in[1000005];
vector<int>ve[1000005],ve2[1000005];
bitset<1005>f[1000005],g[1000005];
queue<int>qu;
struct ee{
    int u,v;
}e[1000005];
struct nd{
    int k,dis,id;
    long double xl;
    friend bool operator<(const nd&a,const nd&b){
        if(a.k!=b.k)return a.k<b.k;
        if(a.xl-b.xl>1e-18||b.xl-a.xl>1e-18)return a.xl-b.xl<1e-18;
        return a.dis<b.dis;
    }
    friend bool operator>(const nd&a,const nd&b){
        return b<a;
    }
}a[1005];
long double slope(int i,int j){
    if(x[i]==x[j]){
        return (int)-1e18;
    }
    return (long double)(y[i]-y[j])/(x[i]-x[j]);
}
int dist(int i,int j){
    return(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
}
int get(int i,int j){
    return(i-1)*n+j;
}
void tarjan(int u){
    low[u]=dfn[u]=++cnt,st[++top]=u,ins[u]=1;
    for(int v:ve[u]){
        if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
        else if(ins[v])low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]){
        cntt++;
        do{
            fr[st[top]]=cntt;
            ins[st[top]]=0;
        }while(st[top--]!=u);
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>t;
    for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
    for(int i=1;i<=n;i++){
        int cnt=0;
        for(int j=1;j<=n;j++)if(i!=j){
            cnt++,a[cnt].dis=dist(i,j),a[cnt].xl=slope(i,j),a[cnt].id=j;
            if(x[j]>x[i]&&y[j]>=y[i])a[cnt].k=1;
            if(x[j]<=x[i]&&y[j]>y[i])a[cnt].k=2;
            if(x[j]<x[i]&&y[j]<=y[i])a[cnt].k=3;
            if(x[j]>=x[i]&&y[j]<y[i])a[cnt].k=4;
        }
        sort(a+1,a+cnt+1);
        for(int j=1;j<=cnt;j++){
            nd xx=a[j];xx.dis=-1e18;
            if(xx.k<=2)xx.k+=2;
            else xx.k-=2;
            int now=lower_bound(a+1,a+cnt+1,xx)-a;
            e[++m]={get(a[j].id,i),get(i,a[(now+t-2)%cnt+1].id)};
            ve[get(a[j].id,i)].emplace_back(get(i,a[(now+t-2)%cnt+1].id));
        }
    }
    for(int i=1;i<=n*n;i++)if(!dfn[i])tarjan(i);
    for(int i=1;i<=n*n;i++)co[fr[i]]++,g[fr[i]][(i-1)/n+1]=1;
    for(int i=1;i<=n*n;i++)if(co[fr[i]]>1)vis[(i-1)/n+1]=1;
    for(int i=1;i<=m;i++)if(fr[e[i].u]!=fr[e[i].v]){
        ve2[fr[e[i].v]].emplace_back(fr[e[i].u]),in[fr[e[i].u]]++;
    }
    for(int i=1;i<=cntt;i++)if(!in[i])qu.push(i);
    while(!qu.empty()){
        int ft=qu.front();qu.pop();
        for(int v:ve2[ft]){
            f[v]|=f[ft],f[v]|=g[ft];
            if(--in[v]==0)qu.push(v);
        }
    }
    for(int i=1;i<=n*n;i++)if(f[fr[i]][(i-1)/n+1]&&!vis[(i-1)/n+1])vis[(i-1)/n+1]=2;
    for(int i=1;i<=n;i++){
        if(vis[i]==1)cout<<"G";
        else if(vis[i]==2)cout<<"B";
        else cout<<"R";
    } 
    return 0;
}