#22859. Longest Path on DAG

题意

这是一道交互题。

给定 $N$ 个编号为 $1\sim N$ 的点，每个点为黑色或白色。存在一张隐藏的有向二分图 $G$，其中每条边 $(u,v)$ 都满足 $u\lt v$，且 $u,v$ 颜色不同。

你可以进行至多 $15000$ 次交互操作，共有两种：

• in u V：选择一个黑点 $u$ 和一个白点集合 $V$，询问是否存在 $v\in V$，使得边 $(v,u)$ 存在。
• out u V：选择一个黑点 $u$ 和一个白点集合 $V$，询问是否存在 $v\in V$，使得边 $(u,v)$ 存在。

你需要通过不超过 $15000$ 次询问，找出并输出图 $G$ 中任意一条最长路径。

$2$ 秒，$1\le N\le 500$。

题解

设黑点集合为 $B$，白点集合为 $W$。

考虑在知道整个图的情况下应该如何求最长路径：对于每个结点 $u$，记录以 $u$ 为终点的最长路径的长度 $f_u$ 和前驱 $pre_u$，那么有 $f_u=\max_{(v,u) \in E} f_v+1$。

对于黑点 $u$，可以直接将 $[1,u)$ 中的白点 $v$ 按照 $f_v$ 排序，通过 $\mathcal O(\log N)$ 次询问，二分求出 $f_v$ 最大的满足 $(v,u) \in E$ 的白点 $v$。

对于白点 $v$，同样需要计算 $[1,v)$ 中所有黑点 $u$ 的 $f_u$ 的最大值，但由于询问格式限制，其至少需要 $\mathcal O(N)$ 次询问来计算。

如果我们对每个白点都这样询问，总询问次数会达到 $\mathcal O(N^2)$，因此我们可以尝试将若干询问合并起来。

对于黑点集合 $B'$ 和白点集合 $W'$ 满足 $\max\{B'\}< \min\{W'\}$，我们考虑如何快速计算 $B'$ 对 $W'$ 的贡献：不断取出 $B'$ 中 $f_u$ 最大的黑点 $u$，并递归找到所有满足 $(u,v) \in E$ 的白点 $v$，用 $f_u+1$ 更新这些白点的 $f_v$，最后将这些白点从 $W'$ 中删除。设 $|W'|=m$，由于每个白点只会被计算一次，所以这样做的询问次数为 $\mathcal O(m \log m)$。

具体实现可以考虑 CDQ 分治：设当前分治区间为 $[l,r]$，我们可以按照如下方式进行计算：

• 如果 $l=r$：
  • 如果 $l$ 为黑点，二分求出 $f_l$ 的值；
  • 如果 $l$ 为白点，$f_l$ 的值在此前已经计算好了。
• 否则：
  • 递归 $[l,mid]$；
  • 对 $[l,mid]$ 中的每个黑点，计算其对 $[mid+1,r]$ 中每个白点的贡献并更新。
  • 递归 $[mid+1,r]$。

总询问次数为 $\mathcal O(N \log^2 N)$，可以通过。

代码

const int N=505;
int n,f[N],pre[N],q[N];
bool s[N],vis[N],ask[N];
pii p[N];
void getb(int u){
    int tot=0;
    for(int v=1;v<u;v++) if(!s[v]) p[++tot]={f[v],v};
    sort(p+1,p+tot+1);
    int l=0,r=tot;
    while(l<r){
        int m=(l+r+1)/2,res;
        cout<<"in "<<u<<' ';
        for(int i=1;i<=n;i++) vis[i]=0;
        for(int i=m;i<=r;i++) vis[p[i].se]=1;
        for(int i=1;i<=n;i++) cout<<vis[i];
        cout<<endl;
        cin>>res;
        if(res==0) r=m-1;
        else l=m;
    }
    f[u]=f[p[r].se]+1,pre[u]=p[r].se;
}
void search(int u,int l,int r){
    int res;
    cout<<"out "<<u<<' ';
    for(int i=1;i<=n;i++) vis[i]=0;
    for(int i=l;i<=r;i++) vis[q[i]]=1;
    for(int i=1;i<=n;i++) cout<<vis[i];
    cout<<endl;
    cin>>res;
    if(!res) return;
    if(l==r){
        if(f[u]+1>f[q[l]]) f[q[l]]=f[u]+1,pre[q[l]]=u;
        ask[q[l]]=0;
    }
    else{
        int m=(l+r)/2;
        search(u,l,m);
        search(u,m+1,r);
    }
}
void getw(int a,int b,int c,int d){
    int tot=0;
    for(int u=a;u<=b;u++) if(s[u]) p[++tot]={f[u],u};
    sort(p+1,p+tot+1);
    for(int i=1;i<=n;i++) ask[i]=0;
    for(int v=c;v<=d;v++) if(!s[v]) ask[v]=1;
    for(int i=tot;i>=1;i--){
        int cnt=0;
        for(int v=c;v<=d;v++) if(ask[v]) q[++cnt]=v;
        search(p[i].se,1,cnt);
    }
}
void dfs(int l,int r){
    if(l==r){
        if(!s[l]) return;
        getb(l);
    }
    else{
        int m=(l+r)>>1;
        dfs(l,m);
        getw(l,m,m+1,r);
        dfs(m+1,r);
    }
}
void print(int u){
    if(!u) return;
    print(pre[u]);
    cout<<u<<' ';
}
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>s[i],f[i]=1,pre[i]=0;
    dfs(1,n);
    int ma=0,u=0;
    for(int i=1;i<=n;i++) if(f[i]>ma) ma=f[i],u=i;
    cout<<"! "<<ma<<' ';
    print(u);
    cout<<endl;
}