Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
32031 | 沈仲恩 | 【S】T3 | C++ | 内存超限 | 90 | 1678 MS | 524308 KB | 2936 | 2024-08-30 14:31:00 |
#include <bits/stdc++.h> #define int long long using namespace std; int n, q, cf[20][200005], val[200005], fa[200005], dpt[200005]; set <int> b[200005], ls; inline void build() { for (int i = 1; i <= 18; i++) for (int j = 1; j <= n; j++) { cf[i][j] = cf[i - 1][cf[i - 1][j]]; } } inline int lca(int x, int y) { if (dpt[x] < dpt[y]) swap(x, y); int jp8ak, cnt; if (dpt[x] != dpt[y]) { jp8ak = dpt[x] - dpt[y], cnt = 0; while (jp8ak) { if (jp8ak & 1) { x = cf[cnt][x]; } cnt++, jp8ak >>= 1; } } cnt = 18; while (cf[cnt][x] == cf[cnt][y]) { cnt--; } while (x != y) { x = cf[cnt][x], y = cf[cnt][y]; cnt--, jp8ak >>= 1; } return x; } signed main() { scanf("%lld", &n); bool cc = (n > 1000); dpt[1] = 1; for (int i = 1; i <= n; i++) { val[i] = dpt[i] = 1; int l;scanf("%lld", &l); if (l != 1) cc = 0; if (cc) { if (l) { int x; scanf("%lld", &x); fa[i] = cf[0][i] = x; dpt[i] = dpt[x] + 1; val[i] = val[x] + 1; } } if (!l) { b[i].insert(i); continue; } int x; scanf("%lld", &x); for (int y : b[x]) b[i].insert(y); l--; while (l--) { scanf("%lld", &x); for (auto it = b[i].begin(); it != b[i].end();) { if (!b[x].count(*it)) { auto it2 = it; it++; b[i].erase(it2); if (it == b[i].end()) break; } else it++; } } // if (i != 1) b[i].insert(i); // printf("B[%lld]: ", i); // for (int j : b[i]) // { // printf("%lld ", j); // } // puts(""); } build(); scanf("%lld", &q); while (q--) { int k; scanf("%lld", &k); ls.clear(); bool vis = 0; int xx; while (k--) { int x; scanf("%lld", &x); if (!cc) { for (int j : b[x]) ls.insert(j); } else { if (!vis) xx = x; else xx = lca(xx, x); } vis = 1; } if (!cc) printf("%ld\n", ls.size()); else printf("%lld\n", val[xx]); } fclose(stdout); return 0; }