QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#207219#6638. TreelectionAlinxesterAC ✓758ms78872kbC++143.0kb2023-10-08 11:29:362023-10-08 11:29:37

Judging History

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

  • [2023-10-08 11:29:37]
  • 评测
  • 测评结果:AC
  • 用时:758ms
  • 内存:78872kb
  • [2023-10-08 11:29:36]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define mod ((int)1e9 + 9)
#define int128 __int128
#define base 23333
#define base2 19260817
#define db double
#define ldb long double
#define eps 1e-8
#define cmpeps 1e-18
#define lowbit(x) (x & -x)
#define un unsigned
#define rep(i,x,y) for (int i = (x); i <= (y); ++i)
#define drep(i,x,y) for (int i = (x); i >= (y); --i)
#define go(i,u) for (int i = head[u]; i; i = edge[i].next)
#define go_(i,u) for (int i = head[u]; ~i; i = edge[i].next)
#define pii pair<int, int>
#define MP make_pair
#define fir first
#define sec second
#define sqr(x) ((x) * (x))
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
using namespace std;
//char buf[1<<21],*p1=buf,*p2=buf;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> inline T rnd(T l,T r) {return uniform_int_distribution<T>(l, r)(rng);}
template<typename T> inline void read (T &t) {
	t = 0; char f = 0, ch = getchar(); ldb d = 0.1;
	while (ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
	while (ch <= '9' && ch >= '0') t = t * 10 + ch - 48, ch = getchar();
	if (ch == '.') {
		ch = getchar();
		while (ch <= '9' && ch >= '0') t += d * (ch ^ 48), d *= 0.1, ch = getchar();
	}
	t = (f ? -t : t);
}
template <typename T, typename... Args>
	inline void read (T& t, Args&... args) { read(t); read(args...); }
inline void write (int x) {
	if (x >= 10) write(x / 10);
	cout << (ll) (x % 10);
}
const int N = 1e6 + 2;
int f[N], g[N], Size[N], fath[N], n;
int head[N], pos;
struct Edge { int to, next; }edge[N << 1];
inline void add_edge (int u, int v) {
	edge[++pos] = (Edge) {v, head[u]}, head[u] = pos; }
inline void get_size (int u) {
	Size[u] = 1;
	go (i, u) {
		int v = edge[i].to;
		get_size(v);
		Size[u] += Size[v];
	}
}
inline void dfs (int u, int x) {
	go (i, u) {
		int v = edge[i].to;
		dfs(v, x);
	}
	if (u > 1) {
		f[u] = max(0ll, f[u] - x);
		//cout << u << " " << fath[u] << " " << f[u] + 1 << '\n';
		f[fath[u]] += f[u] + 1;
	}
}
inline int check (int x) {
	rep (i, 1, n) f[i] = 0;
	dfs(1, x);
	if (f[1] <= x) return 1;
	return 0;
}
inline void pre () {
	rep (i, 1, n) head[i] = g[i] = 0;
	pos = 0;
}
inline void solveg (int u) {
	g[u] = ((g[fath[u]] && f[u]) || (u == 1));
	go (i, u) {
		int v = edge[i].to;
		solveg(v);
	}
}
inline void solve () {
	read(n);
	pre();
	rep (i, 2, n) read(fath[i]), add_edge(fath[i], i);
	get_size(1);
	int l = 1, r = n, ret = n;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid)) ret = mid, r = mid - 1;
		else l = mid + 1;
	}
	//cout << "dkshajashndka : " << '\n';
	rep (i, 1, n) f[i] = 0;
	dfs(1, ret - 1);
	/*cout << ret << '\n';
	rep (i, 1, n) cout << f[i] << " ";
	cout << '\n';*/
	if (f[1] == ret) solveg(1);
	rep (i, 1, n) {
		if (Size[i] > ret + 1 || (Size[i] == ret + 1 && g[i])) printf("1");
		else printf("0");
	}
	printf("\n");
}
signed main () {
	//freo();
	int _ = 1;
	read(_);
	while (_--) solve();
return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
4
1 2 3
5
1 1 2 2

output:

1100
10000

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 87ms
memory: 21344kb

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:

ok 10 lines

Test #3:

score: 0
Accepted
time: 110ms
memory: 62924kb

input:

1
1000000
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:

ok single line: '111111111111111111111111111111...0000000000000000000000000000000'

Test #4:

score: 0
Accepted
time: 501ms
memory: 59832kb

input:

1
1000000
1 2 2 3 5 1 7 3 9 8 4 11 9 6 10 12 10 13 16 18 14 16 7 24 23 21 14 8 26 27 17 21 33 24 20 17 5 34 29 34 37 20 12 22 39 44 33 37 32 27 31 25 30 46 39 26 53 4 11 55 41 29 6 22 32 36 52 57 65 38 59 67 51 56 30 61 36 64 62 19 51 63 53 83 38 75 31 41 49 43 60 18 62 67 91 81 44 25 55 98 86 64 46...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...0000000000000000000000000000000'

Test #5:

score: 0
Accepted
time: 122ms
memory: 21084kb

input:

65764
13
1 1 1 1 1 1 1 1 2 10 10 11
11
1 1 2 2 2 4 4 4 5 10
14
1 2 2 3 3 3 4 4 5 6 10 12 13
14
1 2 2 3 3 3 4 5 5 6 6 7 8
13
1 2 2 3 3 4 5 5 5 6 8 12
13
1 1 1 2 2 3 5 7 7 7 9 9
12
1 1 1 2 2 3 5 7 7 9 10
14
1 1 2 2 3 4 5 6 7 7 8 12 12
14
1 2 3 4 4 5 5 5 7 7 7 10 13
14
1 1 1 1 1 2 2 2 3 10 10 10 11
13
...

output:

1000000000000
11000000000
11101000010000
11100000000000
1110100000000
1010001000000
101000100000
11011001000000
11111010000000
10000000000000
1111010000000
111000100010000
111010001000
11000000000000
11100000000000
11001001000000
11000000000000
11111000000000
110011000000
1010000100000
1100111010000...

result:

ok 65764 lines

Test #6:

score: 0
Accepted
time: 101ms
memory: 61728kb

input:

1
1000000
1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19 19 20 20 21 21 22 22 23 23 24 24 25 25 26 26 27 27 28 28 29 29 30 30 31 31 32 32 33 33 34 34 35 35 36 36 37 37 38 38 39 39 40 40 41 41 42 42 43 43 44 44 45 45 46 46 47 47 48 48 49 49 50 50 51 51 52...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...0000000000000000000000000000000'

Test #7:

score: 0
Accepted
time: 186ms
memory: 78872kb

input:

1
1000000
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:

ok single line: '111111111111111111111111111111...1111111111111111111111111111100'

Test #8:

score: 0
Accepted
time: 89ms
memory: 61884kb

input:

1
1000000
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok single line: '100000000000000000000000000000...0000000000000000000000000000000'

Test #9:

score: 0
Accepted
time: 131ms
memory: 18528kb

input:

100
10000
1 1 2 4 1 4 4 5 6 6 1 1 10 13 3 7 7 16 11 2 15 2 19 21 5 6 8 20 12 10 9 28 14 24 30 1 8 11 1 16 34 4 10 13 25 16 6 11 16 11 2 40 1 47 24 15 29 35 21 49 8 33 26 54 46 52 48 32 54 56 11 55 7 28 30 20 4 7 58 61 65 77 65 21 82 9 22 29 3 19 3 59 26 90 48 21 89 86 95 12 98 43 30 21 59 56 43 37 6...

output:

111111111111111111111111111111111111111111101111111111111111111111111111111111111111111011111111111111111110101101111111110110101101111111111111111111111111111011011111111111111101111011110111111101011111101101111110111111011110111110011110111011001111111011110111000100010110111110101011111110110110...

result:

ok 100 lines

Test #10:

score: 0
Accepted
time: 381ms
memory: 20912kb

input:

10
100000
1 1 2 2 5 3 2 6 6 5 9 11 11 5 12 9 10 10 4 7 17 8 13 14 3 12 21 22 3 4 31 12 15 25 27 7 27 11 39 37 27 34 18 14 4 42 47 24 47 39 50 28 46 53 16 15 57 20 7 58 57 25 6 58 36 63 49 46 24 59 19 57 63 24 31 54 16 75 58 26 37 50 10 77 51 54 13 42 22 21 48 71 65 34 34 89 89 67 19 74 30 49 70 60 1...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok 10 lines

Test #11:

score: 0
Accepted
time: 516ms
memory: 61812kb

input:

1
1000000
1 2 3 3 1 4 4 8 8 9 8 7 3 6 14 5 14 16 14 12 21 19 18 22 17 20 22 28 4 13 30 15 20 5 18 2 6 7 29 16 39 2 26 21 25 12 38 15 6 39 45 13 17 21 23 27 57 48 11 23 47 23 45 29 59 26 11 57 40 69 48 71 12 58 38 76 32 49 10 71 44 67 20 69 35 64 44 51 77 48 30 41 91 73 78 90 97 5 65 54 16 31 17 81 6...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...0000000000000000000000000000000'

Test #12:

score: 0
Accepted
time: 113ms
memory: 14204kb

input:

100
10000
1 2 2 4 1 5 7 4 6 2 6 10 11 13 14 3 17 4 8 18 8 7 16 12 12 20 27 27 21 12 21 25 19 32 30 33 13 21 16 30 7 36 25 13 11 6 40 14 45 40 14 39 26 3 48 56 35 49 38 31 58 56 10 51 39 59 46 26 59 55 51 44 63 16 23 15 32 50 59 43 67 57 41 30 10 72 60 17 19 41 22 78 73 29 33 27 74 57 65 100 36 68 81...

output:

111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111101111110111111111111111111111011111111111111111111111110111101110111110111111111111111010111111111111001111111111111111111111101101111111111111101111011111011...

result:

ok 100 lines

Test #13:

score: 0
Accepted
time: 363ms
memory: 20988kb

input:

10
100000
1 1 3 3 4 3 1 2 8 10 7 6 10 12 2 2 14 10 13 10 16 9 15 21 23 18 23 27 3 9 9 5 25 29 11 32 5 38 19 9 34 21 38 15 39 34 24 33 25 44 19 15 22 25 38 18 5 35 8 50 19 15 4 16 21 50 32 50 12 29 68 27 13 49 54 18 62 45 30 37 79 7 82 32 70 79 27 78 41 33 43 17 13 2 82 44 21 29 63 27 101 96 97 50 35...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111...

result:

ok 10 lines

Test #14:

score: 0
Accepted
time: 520ms
memory: 59756kb

input:

1
1000000
1 1 2 4 4 4 6 3 3 6 3 12 11 2 7 12 6 4 1 20 13 16 6 11 25 19 25 21 22 3 21 25 29 30 13 20 12 28 16 37 20 17 16 22 40 2 36 17 43 31 21 38 27 48 50 25 22 26 17 24 49 11 51 47 47 29 31 15 24 68 29 50 48 17 59 47 76 69 9 50 44 41 29 21 36 72 78 40 70 61 13 14 13 85 24 20 93 80 67 8 96 73 86 9 ...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...0000000000000000000000000000000'

Test #15:

score: 0
Accepted
time: 117ms
memory: 14160kb

input:

100
10000
1 2 1 2 3 2 6 5 6 7 7 4 7 11 8 6 15 10 8 1 4 5 10 7 16 11 20 27 19 1 3 8 30 22 18 29 27 29 21 25 12 29 30 24 5 8 28 16 39 43 1 2 53 43 21 36 41 37 41 45 4 4 49 56 49 39 21 27 58 64 53 58 57 57 31 32 56 46 17 8 29 8 3 20 4 29 72 67 24 74 51 52 34 92 75 78 13 3 15 37 89 58 31 54 28 71 103 88...

output:

111111111111111111111111111111111111111011111111101111111111111111111011111011111111111111011111111111110111111111101011111111111011111111111101111111000111100111010111111101010101111110111011100111111101101111111110011111111111111111111101010101111100010111111111100011011010001110110111111101111101...

result:

ok 100 lines

Test #16:

score: 0
Accepted
time: 423ms
memory: 43568kb

input:

2
500000
1 2 3 2 5 4 7 1 8 9 10 7 10 9 12 4 5 16 3 11 6 11 13 21 25 6 16 13 15 19 28 19 30 33 26 32 34 26 21 14 39 41 27 40 39 12 37 17 31 27 37 18 32 31 28 44 34 44 23 24 41 52 57 29 45 54 48 18 47 52 70 71 49 24 48 54 51 29 66 61 60 82 70 23 79 64 50 60 45 17 63 47 25 86 57 51 14 40 98 30 35 59 35...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok 2 lines

Test #17:

score: 0
Accepted
time: 307ms
memory: 20772kb

input:

10
100000
1 2 2 3 3 6 1 4 9 8 9 7 11 7 4 13 5 6 10 8 19 15 21 14 19 22 17 28 21 25 29 12 10 20 27 24 33 22 25 26 5 18 36 28 18 14 42 35 47 34 27 43 39 40 46 38 24 42 57 29 47 36 54 61 59 31 62 41 30 53 65 23 45 49 71 72 73 52 48 61 57 37 13 31 40 15 17 77 20 75 48 67 35 33 49 77 89 46 65 56 34 32 95...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok 10 lines

Test #18:

score: 0
Accepted
time: 111ms
memory: 14132kb

input:

100
10000
1 1 2 4 4 3 7 8 6 5 10 5 13 10 15 16 11 14 8 11 7 6 22 9 17 2 9 13 16 27 15 20 30 21 24 35 29 34 37 40 28 40 19 20 32 41 28 45 17 21 32 47 45 31 37 35 27 53 26 19 44 58 38 49 59 24 36 42 62 57 12 18 48 31 18 62 46 46 63 33 36 64 59 60 66 79 58 86 77 54 76 86 82 63 43 53 87 76 47 77 64 30 7...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok 100 lines

Test #19:

score: 0
Accepted
time: 758ms
memory: 59760kb

input:

1
1000000
1 2 3 1 1 6 6 7 7 5 5 12 10 11 6 16 4 7 5 17 14 19 6 1 7 16 9 15 9 21 30 25 6 7 34 32 32 26 25 19 29 1 42 44 32 39 7 43 4 22 28 22 52 25 38 43 52 17 11 9 21 36 28 54 13 17 53 52 62 69 9 3 37 69 47 8 44 9 19 5 44 21 18 14 15 22 19 71 60 25 6 88 29 94 4 30 29 88 74 55 63 31 21 9 23 4 80 35 1...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111111110111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...0000000000000000000000000000000'