MLE && TLE,请DL帮助
查看原帖
MLE && TLE,请DL帮助
244309
yuhaocheng楼主2022/3/2 21:26
#include <cstdio>
#include <vector>
using namespace std;

inline int read() {
    int __x = 0, __f = 1;
    char __c = getchar();
    while(__c < '0' || __c > '9') {
        if (__c == '-')
            __f = -1;
        __c = getchar();
    }
    while(__c >= '0' && __c <= '9') {
        __x = __x * 10 + __c - '0';
        __c = getchar();
    }
    return __x * __f;
}
char __F[11];
inline void write(int __x) {
    if(__x == 0) {
        putchar('0');
        return;
    }
    int __tmp, __cnt = 0;
    if(__x > 0) {
        __tmp = __x;
    } else {
        __tmp = -__x;
    }
    if(__x < 0) {
        putchar('-');
    }
    while(__tmp > 0) {
        __F[__cnt++] = __tmp % 10 + '0';
        __tmp /= 10;
    }
    while(__cnt > 0) {
        putchar(__F[--__cnt]);
    }
}

const int maxn = 5e6 + 1;

int n, m;
struct Node {
    int fa;
    vector<int> ch;
} tree[maxn];
int f1[maxn]; // max
int pf1[maxn];
int pf2[maxn];
int d[maxn];

int dfs_f(int x, int dep) {
    f1[x] = dep;
    d[x] = dep;
    for(int c : tree[x].ch) {
        int ret = dfs_f(c, dep + 1);
        f1[x] = max(f1[x], ret);
        if(ret >= f1[pf1[x]]) {
            pf2[x] = pf1[x];
            pf1[x] = c;
        } else if(ret > f1[pf2[x]]) {
            pf2[x] = c;
        }
    }
    return f1[x];
}

int dfs(int x, int k) {
    if(f1[pf2[x]] >= k) {
        return x;
    } else if(d[x] >= k) {
        return x;
    }
    return dfs(pf1[x], k);
}

int ans[maxn];
int k;

int main() {
    n = read();
    m = read();
    for(int i = 1; i <= n; i++) {
        tree[i].fa = read();
        tree[tree[i].fa].ch.push_back(i);
    }
    dfs_f(1, 1);
    ans[0] = 1;
    for(int i = 1; i <= f1[1]; i++) {
        ans[i] = dfs(ans[i - 1], i);
    }
    for(int i = 1; i <= m; i++) {
        k = read();
        write(ans[k]);
        puts("");
    }
}

record: https://www.luogu.com.cn/record/70438221

2022/3/2 21:26
加载中...