M_sea

CF1129E Legendary Tree
CodeForcesLuogu分析神仙题。钦定 $1$ 为根节点,那么可以通过 $n-1$ 次询问得到每个点的子树...
扫描右侧二维码阅读全文
23
2019/04

CF1129E Legendary Tree

CodeForces

Luogu

分析

神仙题。

钦定 $1$ 为根节点,那么可以通过 $n-1$ 次询问得到每个点的子树的 $size$ 。

具体方法是,对于第 $i$ 个点询问 $(\{1\},\big\{U-\{1\}-\{i\}\big\},i)$ ,返回的值就是 $size[i]$ 。

把 $[2,n]$ 按 $size$ 从小到大排序,这样子 $i$ 的儿子一定在 $i$ 左边。

我们把所有的没有确定父亲的点存在一个 $\mathrm{set}$ 里面。

从左往右处理这个序列。首先如果当前点有儿子,就找;然后把它加到 $\mathrm{set}$ 里面。

找儿子的过程是这样的:首先把当前的 $\mathrm{set}$ 分成两半,如果左边有子节点就往左边走,右边一样处理。

这样子可以找到儿子。把儿子的父亲记下来,然后从 $\mathrm{set}$ 中删去即可。

询问次数最多的点在 $6000$ 次左右。

建议画图理解。具体实现及细节见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#define re register
#define IT set<int>::iterator
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500+10;

int fa[N],sz[N],p[N];
set<int> S;

inline bool cmp(int a,int b) { return sz[a]<sz[b]; }

inline void solve(int u,IT it,int tot) {
    if (tot==1) { fa[*it]=u; S.erase(it); return; }
    int mid=tot>>1; IT p=it;
    
    printf("1\n1\n%d\n",mid);
    for (re int i=1;i<=mid;++i,++p) printf("%d ",*p);
    printf("\n%d\n",u);
    fflush(stdout);
    if (read()) solve(u,it,mid);

    it=p; printf("1\n1\n%d\n",tot-mid);
    for (re int i=mid+1;i<=tot;++i,++p) printf("%d ",*p);
    printf("\n%d\n",u);
    fflush(stdout);
    if (read()) solve(u,it,tot-mid);
}

int main() {
    int n=read();
    if (n==2) { puts("ANSWER\n1 2"); return 0; }
    for (re int i=2;i<=n;++i) {
        printf("1\n%d\n%d\n",1,n-2);
        for (re int j=2;j<=n;++j)
            if (i!=j) printf("%d ",j);
        printf("\n%d\n",i);
        fflush(stdout);
        sz[i]=read();
    }
    for (re int i=2;i<=n;++i) p[i]=i;
    sort(p+2,p+n+1,cmp);
    for (re int i=2;i<=n;++i) {
        int u=p[i];
        if (!sz[u]) { S.insert(u); continue; }
        solve(u,S.begin(),S.size()); S.insert(u);
    }
    for (IT it=S.begin();it!=S.end();++it) fa[*it]=1;
    puts("ANSWER");
    for (re int i=2;i<=n;++i) printf("%d %d\n",fa[i],i);
    return 0;
}
最后修改:2019 年 05 月 26 日 09 : 40 PM

2 条评论

  1. smy

    神_sea Tree!!!

    1. M_sea
      @smy

      神my Tree!!!!

发表评论