#include "september.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXN = 100000 + 10;
const int INF = 1e9;
int n, m;
struct Fenwick
{
int tree[MAXN];
void reset()
{
std::fill(tree, tree + n + 1, 0);
}
void update(int idx, int val)
{
for (; idx <= n ; idx += idx & (-idx))
{
tree[idx] += val;
}
}
int query(int idx)
{
int res = 0;
for (; idx ; idx -= idx & (-idx))
{
res += tree[idx];
}
return res;
}
void rangeUpdate(int l, int r)
{
update(l, 1);
update(r + 1, -1);
}
int query(int l, int r)
{
return query(r) - query(l - 1);
}
};
bool added[MAXN];
Fenwick childTree;
Fenwick parentTree;
std::vector <int> g[MAXN];
int count[MAXN];
int count2[MAXN];
int in[MAXN];
int out[MAXN];
int timer;
void dfs(int node)
{
in[node] = ++timer;
for (const int &u : g[node])
{
dfs(u);
}
out[node] = timer;
}
int solve(int N, int M, std::vector<int> F, std::vector<std::vector<int>> S)
{
n = N;
m = M;
for (int i = 1 ; i <= n ; ++i)
{
g[i].clear();
added[i] = 0;
count[i] = count2[i] = 0;
}
for (int i = 1 ; i < n ; ++i)
{
g[F[i] + 1].push_back(i + 1);
}
childTree.reset();
parentTree.reset();
timer = 0;
dfs(1);
for (int i = 1 ; i <= n ; ++i)
{
childTree.update(i, 1);
}
int badCnt = 0;
int answer = 0;
for (int i = 0 ; i < n - 1 ; ++i)
{
for (int person = 0 ; person < m ; ++person)
{
S[person][i]++;
int node = S[person][i];
count2[count[node]]--;
count[node]++;
count2[count[node]]++;
if (!added[node])
{
badCnt += childTree.query(in[node], out[node]);
childTree.update(in[node], -1);
parentTree.rangeUpdate(in[node], out[node]);
badCnt -= parentTree.query(in[node]);
added[node] = true;
}
}
if (badCnt == 0 && count2[m] == i + 1)
{
answer++;
}
}
return answer;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
2 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
1 ms |
4444 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
17 |
Correct |
1 ms |
4444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
2 ms |
4444 KB |
Output is correct |
5 |
Correct |
2 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
2 ms |
4444 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
17 |
Correct |
1 ms |
4444 KB |
Output is correct |
18 |
Correct |
1 ms |
4444 KB |
Output is correct |
19 |
Correct |
1 ms |
4444 KB |
Output is correct |
20 |
Correct |
1 ms |
4444 KB |
Output is correct |
21 |
Correct |
1 ms |
4444 KB |
Output is correct |
22 |
Correct |
1 ms |
4444 KB |
Output is correct |
23 |
Correct |
1 ms |
4444 KB |
Output is correct |
24 |
Correct |
1 ms |
4444 KB |
Output is correct |
25 |
Correct |
2 ms |
4444 KB |
Output is correct |
26 |
Correct |
2 ms |
4444 KB |
Output is correct |
27 |
Correct |
1 ms |
4444 KB |
Output is correct |
28 |
Correct |
2 ms |
4440 KB |
Output is correct |
29 |
Correct |
2 ms |
4444 KB |
Output is correct |
30 |
Correct |
1 ms |
4444 KB |
Output is correct |
31 |
Correct |
2 ms |
4444 KB |
Output is correct |
32 |
Correct |
2 ms |
4444 KB |
Output is correct |
33 |
Correct |
2 ms |
4444 KB |
Output is correct |
34 |
Correct |
1 ms |
4444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
121 ms |
12516 KB |
Output is correct |
5 |
Correct |
124 ms |
12548 KB |
Output is correct |
6 |
Correct |
123 ms |
12544 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
2 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
1 ms |
4444 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
17 |
Correct |
1 ms |
4444 KB |
Output is correct |
18 |
Correct |
121 ms |
12516 KB |
Output is correct |
19 |
Correct |
124 ms |
12548 KB |
Output is correct |
20 |
Correct |
123 ms |
12544 KB |
Output is correct |
21 |
Correct |
160 ms |
9444 KB |
Output is correct |
22 |
Correct |
172 ms |
9388 KB |
Output is correct |
23 |
Correct |
154 ms |
10164 KB |
Output is correct |
24 |
Correct |
153 ms |
10156 KB |
Output is correct |
25 |
Correct |
166 ms |
9512 KB |
Output is correct |
26 |
Correct |
164 ms |
9388 KB |
Output is correct |
27 |
Correct |
154 ms |
10176 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
2 ms |
4444 KB |
Output is correct |
5 |
Correct |
2 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
121 ms |
12516 KB |
Output is correct |
8 |
Correct |
124 ms |
12548 KB |
Output is correct |
9 |
Correct |
123 ms |
12544 KB |
Output is correct |
10 |
Correct |
65 ms |
15560 KB |
Output is correct |
11 |
Correct |
63 ms |
15564 KB |
Output is correct |
12 |
Correct |
65 ms |
15692 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4444 KB |
Output is correct |
3 |
Correct |
1 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4444 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
11 |
Correct |
1 ms |
4444 KB |
Output is correct |
12 |
Correct |
1 ms |
4444 KB |
Output is correct |
13 |
Correct |
1 ms |
4444 KB |
Output is correct |
14 |
Correct |
1 ms |
4444 KB |
Output is correct |
15 |
Correct |
2 ms |
4444 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
17 |
Correct |
1 ms |
4444 KB |
Output is correct |
18 |
Correct |
1 ms |
4444 KB |
Output is correct |
19 |
Correct |
1 ms |
4444 KB |
Output is correct |
20 |
Correct |
1 ms |
4444 KB |
Output is correct |
21 |
Correct |
1 ms |
4444 KB |
Output is correct |
22 |
Correct |
1 ms |
4444 KB |
Output is correct |
23 |
Correct |
1 ms |
4444 KB |
Output is correct |
24 |
Correct |
1 ms |
4444 KB |
Output is correct |
25 |
Correct |
2 ms |
4444 KB |
Output is correct |
26 |
Correct |
2 ms |
4444 KB |
Output is correct |
27 |
Correct |
1 ms |
4444 KB |
Output is correct |
28 |
Correct |
2 ms |
4440 KB |
Output is correct |
29 |
Correct |
2 ms |
4444 KB |
Output is correct |
30 |
Correct |
1 ms |
4444 KB |
Output is correct |
31 |
Correct |
2 ms |
4444 KB |
Output is correct |
32 |
Correct |
2 ms |
4444 KB |
Output is correct |
33 |
Correct |
2 ms |
4444 KB |
Output is correct |
34 |
Correct |
1 ms |
4444 KB |
Output is correct |
35 |
Correct |
121 ms |
12516 KB |
Output is correct |
36 |
Correct |
124 ms |
12548 KB |
Output is correct |
37 |
Correct |
123 ms |
12544 KB |
Output is correct |
38 |
Correct |
160 ms |
9444 KB |
Output is correct |
39 |
Correct |
172 ms |
9388 KB |
Output is correct |
40 |
Correct |
154 ms |
10164 KB |
Output is correct |
41 |
Correct |
153 ms |
10156 KB |
Output is correct |
42 |
Correct |
166 ms |
9512 KB |
Output is correct |
43 |
Correct |
164 ms |
9388 KB |
Output is correct |
44 |
Correct |
154 ms |
10176 KB |
Output is correct |
45 |
Correct |
65 ms |
15560 KB |
Output is correct |
46 |
Correct |
63 ms |
15564 KB |
Output is correct |
47 |
Correct |
65 ms |
15692 KB |
Output is correct |
48 |
Correct |
74 ms |
11424 KB |
Output is correct |
49 |
Correct |
71 ms |
11468 KB |
Output is correct |
50 |
Correct |
72 ms |
12244 KB |
Output is correct |
51 |
Correct |
69 ms |
12244 KB |
Output is correct |
52 |
Correct |
75 ms |
11456 KB |
Output is correct |
53 |
Correct |
70 ms |
11468 KB |
Output is correct |
54 |
Correct |
68 ms |
12232 KB |
Output is correct |