QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#488031#6638. Treelectionucup-team052#WA 186ms19020kbC++231.2kb2024-07-23 15:24:162024-07-23 15:24:16

Judging History

你现在查看的是最新测评结果

  • [2024-07-23 15:24:16]
  • 评测
  • 测评结果:WA
  • 用时:186ms
  • 内存:19020kb
  • [2024-07-23 15:24:16]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;

vector <int> adj[N];
int fa[N], siz[N], ans[N];
int T, n;

void dfs1(int u) {
	siz[u] = 1;
	for (auto v : adj[u]) {
		dfs1(v);
		siz[u] += siz[v];
	}
}

int f[N], MID;
void dfs2(int u) {
	f[u] = 0;
	for (auto v : adj[u]) {
		dfs2(v);
		f[u] += f[v];
	}
	f[u] = max(0, f[u] - MID) + (u != 1);
}

int ok[N];
void dfs3(int u) {
	if (f[u] <= 1) return;
	ok[u] = 1;
	for (auto v : adj[u]) dfs3(v);
}

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) {
			adj[i].clear();
			ok[i] = 0;
		}
		for (int i = 2; i <= n; i++) {
			scanf("%d", &fa[i]);
			adj[fa[i]].push_back(i);
		}
		dfs1(1);
		int l = 1, r = n - 1, res = n - 1;
		while (l <= r) {
			int mid = (l + r) >> 1;
			MID = mid; dfs2(1);
			if (f[1] <= 1) res = mid, r = mid - 1;
			else l = mid + 1;
		}
		MID = res; dfs2(1);
		if (f[1] == 1) {
			for (auto v : adj[1]) dfs3(v);
		}
		for (int u = 1; u <= n; u++) {
			int ans = 0;
			if (siz[u] - 1 > res) ans = 1;
			else if (siz[u] - 1 == res) ans = ok[u];
			printf("%d", ans);
		}
		printf("\n");
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 12136kb

input:

2
4
1 2 3
5
1 1 2 2

output:

1100
10000

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 186ms
memory: 19020kb

input:

10
100000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 10...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

wrong answer 1st lines differ - expected: '111111111111111111111111111111...0000000000000000000000000000000', found: '111111111111111111111111111111...0000000000000000000000000000000'