AC代码

const int N = 2005;
int dep[N], n;
int fa[N];
struct Info
{
    int st = 0;
    vector<int> *s;
    Info(int _s = 0) : st(_s) { s = new vector<int>[n - _s + 3]; };
    inline vector<int> &operator[](int x)
    {
        return s[x - st];
    }
};
void solve(int p, Info bel)
{
    int d = dep[p];
    if (bel[d + 1].size() == 0)
        return;
    if (bel[d + 2].size() == 0)
        return;
    else
    {
        if (bel[d + 1].size() * bel[d + 2].size() > n)
            for (int s : bel[d + 1])
            {
                Info tmp(d);
                printf("? 2 %d\n", s), fflush(stdout);
                int n = read();
                for (int i = 1, a; i <= n; ++i)
                    read(a), tmp[dep[a]].push_back(a);
                for (int i : tmp[d + 2])
                    fa[i] = s;
                solve(s, tmp);
            }
        else
        {
            for (int a : bel[d + 1])
                for (int b : bel[d + 2])
                {
                    printf("? 1 %d %d\n", a, b), fflush(stdout);
                    if (read() == 1)
                        fa[b] = a;
                }
            solve(bel[d + 1].front(), bel);
        }
    }
}
signed main()
{
    read(n);
    for (int i = 2; i <= n; ++i)
        printf("? 1 1 %d\n", i), fflush(stdout), read(dep[i]);
    Info rt;
    for (int i = 1; i <= n; ++i)
        rt[dep[i]].push_back(i);
    for (int i : rt[1])
        fa[i] = 1;
    solve(1, rt);
    printf("! ");
    for (int i = 2; i <= n; ++i)
        write(fa[i]);
    return 0;
}

MLE代码

const int N = 2005;
int dep[N], n;
int fa[N];
struct Info
{
    vector<int> s[N];
};
void solve(int p, Info bel)
{
    int d = dep[p];
    if (bel.s[d + 1].size() == 0)
        return;
    if (bel.s[d + 2].size() == 0)
        return;
    else
    {
        if (bel.s[d + 1].size() * bel.s[d + 2].size() > n)
            for (int s : bel.s[d + 1])
            {
                Info tmp;
                printf("? 2 %d\n", s), fflush(stdout);
                int n = read();
                for (int i = 1, a; i <= n; ++i)
                    read(a), tmp.s[dep[a]].push_back(a);
                for (int i : tmp.s[d + 2])
                    fa[i] = s;
                solve(s, tmp);
            }
        else
        {
            for (int a : bel.s[d + 1])
                for (int b : bel.s[d + 2])
                {
                    printf("? 1 %d %d\n", a, b), fflush(stdout);
                    if (read() == 1)
                        fa[b] = a;
                }
            solve(bel.s[d + 1].front(), bel);
        }
    }
}
signed main()
{
    read(n);
    for (int i = 2; i <= n; ++i)
        printf("? 1 1 %d\n", i), fflush(stdout), read(dep[i]);
    Info rt;
    for (int i = 1; i <= n; ++i)
        rt.s[dep[i]].push_back(i);
    for (int i : rt.s[1])
        fa[i] = 1;
    solve(1, rt);
    printf("! ");
    for (int i = 2; i <= n; ++i)
        write(fa[i]);
    return 0;
}

只重载了一个运算符，稍微压了一下空间常数，理论不应出现过大差别。但MLE掉的点在AC代码上只用了1MB不到的内存。