【站务必看】社区站务汇总
2024-07-09 14:47:18
发布于：浙江
887阅读
0回复
0点赞
目录
请不要回复本帖
请不要回复本帖
请不要回复本帖
全部评论 16
续举报ID：4270748 当时做题的源代码：
merge(come[u], las), ++out[come[u]], ++in[las]; las = come[u] ^ 1, u = fa[u]; } st[p[i]] = las; break; } } for (int i = 1; i <= N; ++i) printf("%d ", ans[i]); putchar('\n'); for (int i = 1; i <= N; ++i) head[i] = st[i] = ed[i] = deg[i] = used[i] = ans[i] = 0; for (int i = 1; i <= Elen; ++i) in[i] = out[i] = 0; Elen = 1; } return 0; }2024-09-15 来自 浙江
0ID：4270748
在2024-09-14 20:37:38做的 A41.树上的数 用时61秒，但代码所用时间不合理
以下为ID：4270748在做 A41.树上的数 的源代码：#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 100005; int F[MAXN << 1], siz[MAXN], st[MAXN], ed[MAXN], in[MAXN], out[MAXN]; int get(int x) { if (F[x] != x) F[x] = get(F[x]); return F[x]; } void merge(int x, int y) { x = get(x), y = get(y); if (siz[x] > siz[y]) swap(x, y); siz[y] += siz[x], F[x] = y; } int T, N, p[MAXN], ans[MAXN], deg[MAXN]; struct node { int v, next; } E[MAXN << 1]; int head[MAXN], Elen = 1; void add(int u, int v) { ++Elen, E[Elen].v = v, E[Elen].next = head[u], head[u] = Elen, F[Elen] = Elen, siz[Elen] = 1; } bool ok[MAXN], used[MAXN]; int fa[MAXN], come[MAXN]; void dfs(int u, int ff, int com) { come[u] = com, fa[u] = ff; if (!ff) { for (int i = head[u]; i; i = E[i].next) if (!st[u] && !in[i] && (!ed[u] || get(ed[u]) != get(i) || siz[get(ed[u])] == deg[u])) dfs(E[i].v, u, i ^ 1); } else { if (!ed[u] && !out[com] && (!st[u] || get(st[u]) != get(com) || siz[get(st[u])] == deg[u])) ok[u] = 1; for (int i = head[u]; i; i = E[i].next) if (E[i].v != ff) { if (get(i) != get(com) && !in[i] && !out[com] && i != st[u] && com != ed[u]) { if (get(com) == get(st[u]) && get(i) == get(ed[u]) || get(com) == get(ed[u]) && get(i) == get(st[u])) { if (siz[get(st[u])] + siz[get(ed[u])] != deg[u]) continue; } dfs(E[i].v, u, i ^ 1); } } } } int main() { scanf("%d", &T); while (T--) { scanf("%d", &N); int u, v; for (int i = 1; i <= N; ++i) scanf("%d", &p[i]); for (int i = 1; i < N; ++i) scanf("%d%d", &u, &v), add(u, v), add(v, u), ++deg[u], ++deg[v]; for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) ok[j] = 0; dfs(p[i], 0, 0); for (int j = 1; j <= N; ++j) if (j != p[i] && !used[j] && ok[j]) { ans[i] = j, ed[j] = come[j], used[j] = 1; int las = come[j] ^ 1; u = fa[j]; while (u != p[i]) { merge(come[u], las), ++out[come[u]], ++in[las];2024-09-15 来自 浙江
0
有帮助，赞一个