Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
32036 沈仲恩 【S】T3 C++ 编译错误 0 0 MS 0 KB 3796 2024-08-30 14:42:57

Tests(0/0):


#include <bits/stdc++.h> #define int long long using namespace std; int n, q, cf[20][200005], val[200005], fa[200005], dpt[200005]; int sz[200005]; vector <int> aa[200005]; 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() { // freopen("set.in", "r", stdin); // freopen("set.out", "w", stdout); scanf("%lld", &n); bool cc = (n > 1000); dpt[1] = 1; for (int i = 1; i <= n; i++) { scanf("%lld", &sz[i]); if (sz[i] > 1) cc = 0; for (int j = 1; j <= sz[i]; j++) { int k; scanf("%lld", &k); aa[i][j].push_back(k); } } if (cc) { for (int i = 1; i <= n; i++) { if (sz[i]) { int x = aa[i][0]; fa[i] = cf[0][i] = x; dpt[i] = dpt[x] + 1; val[i] = val[x] + 1; } } build(); scanf("%lld", &q); while (q--) { int k; scanf("%lld", &k); if (!k) printf("0\n"); int ll; bool vis = 0; while (k--) { int x; scanf("%lld", &x); if (!vis) ll = x; else ll = lca(ll, x); } printf("%lld\n", val[ll]); } } else { set <int> b[200005], ls; for (int i = 1; i <= n; i++) { val[i] = dpt[i] = 1; int l;scanf("%lld", &l); 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(""); } scanf("%lld", &q); while (q--) { int k; scanf("%lld", &k); ls.clear(); bool vis = 0; int xx; while (k--) { int x; scanf("%lld", &x); for (int j : b[x]) ls.insert(j); vis = 1; } printf("%ld\n", ls.size()); } } fclose(stdout); return 0; }


测评信息: