// failed/subtask-smallN-wa2.cpp
#include "beechtree.h"
#include <set>
#include <algorithm>
using namespace std;
using pii = pair<int, int>;
int n, m;
vector<int> par, sz;
vector<set<int>> ch_colors;
vector<int> t;
bool is_subset(int x, int y)
{
if (sz[x] > sz[y])
swap(x, y);
if (sz[x] == sz[y] && ch_colors[x].size() != ch_colors[y].size())
return false;
if (ch_colors[x].size() > ch_colors[y].size())
return false;
for (int c : ch_colors[x])
{
if (!ch_colors[y].count(c))
return false;
}
return true;
}
void solve(int r)
{
vector<int> subtree = {r};
for (int u = r + 1; u < n; ++u)
{
if (ch_colors[u].size() == 0)
continue;
if (binary_search(subtree.begin(), subtree.end(), par[u]))
{
if (t[u] == 0)
{
t[r] = 0;
return;
}
subtree.push_back(u);
}
}
int k = subtree.size();
for (int i = 0; i + 1 < k; ++i)
{
for (int j = i + 1; j < k; ++j)
{
int x = subtree[i], y = subtree[j];
if (!is_subset(x, y))
{
t[r] = 0;
return;
}
}
}
}
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
n = N, m = M, par = P;
ch_colors.assign(N, {});
t.assign(N, 1);
for (int v = 1; v < N; ++v)
{
int u = P[v];
if (ch_colors[u].count(C[v]))
{
t[u] = 0;
}
ch_colors[u].insert(C[v]);
}
for (int v = 1; v < N; ++v)
{
if (ch_colors[v].size() > ch_colors[P[v]].size())
t[P[v]] = 0;
}
sz.assign(N, 1);
for (int r = N - 1; r >= 0; --r)
{
if (r > 0)
sz[P[r]] += sz[r];
solve(r);
}
return t;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1308 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1664 KB |
Output is correct |
2 |
Correct |
2 ms |
1580 KB |
Output is correct |
3 |
Correct |
1 ms |
1044 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
228 KB |
Output is correct |
6 |
Correct |
2 ms |
1536 KB |
Output is correct |
7 |
Correct |
1 ms |
388 KB |
Output is correct |
8 |
Correct |
0 ms |
228 KB |
Output is correct |
9 |
Correct |
1 ms |
372 KB |
Output is correct |
10 |
Correct |
0 ms |
228 KB |
Output is correct |
11 |
Correct |
1 ms |
228 KB |
Output is correct |
12 |
Correct |
0 ms |
228 KB |
Output is correct |
13 |
Correct |
1 ms |
228 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Incorrect |
1 ms |
212 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
19 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1664 KB |
Output is correct |
2 |
Correct |
2 ms |
1580 KB |
Output is correct |
3 |
Correct |
1 ms |
1044 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
228 KB |
Output is correct |
6 |
Correct |
2 ms |
1536 KB |
Output is correct |
7 |
Correct |
79 ms |
27824 KB |
Output is correct |
8 |
Correct |
69 ms |
27864 KB |
Output is correct |
9 |
Correct |
8 ms |
228 KB |
Output is correct |
10 |
Correct |
1 ms |
228 KB |
Output is correct |
11 |
Correct |
1 ms |
228 KB |
Output is correct |
12 |
Correct |
0 ms |
228 KB |
Output is correct |
13 |
Execution timed out |
2056 ms |
544 KB |
Time limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
3 ms |
340 KB |
Output is correct |
12 |
Correct |
2 ms |
464 KB |
Output is correct |
13 |
Correct |
3 ms |
464 KB |
Output is correct |
14 |
Correct |
3 ms |
340 KB |
Output is correct |
15 |
Execution timed out |
2041 ms |
12872 KB |
Time limit exceeded |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1664 KB |
Output is correct |
2 |
Correct |
2 ms |
1580 KB |
Output is correct |
3 |
Correct |
1 ms |
388 KB |
Output is correct |
4 |
Correct |
0 ms |
228 KB |
Output is correct |
5 |
Correct |
79 ms |
27824 KB |
Output is correct |
6 |
Correct |
69 ms |
27864 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
7 ms |
468 KB |
Output is correct |
10 |
Correct |
6 ms |
468 KB |
Output is correct |
11 |
Execution timed out |
2057 ms |
23660 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1308 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
224 KB |
Output is correct |
4 |
Correct |
2 ms |
1664 KB |
Output is correct |
5 |
Correct |
2 ms |
1580 KB |
Output is correct |
6 |
Correct |
1 ms |
1044 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
228 KB |
Output is correct |
9 |
Correct |
2 ms |
1536 KB |
Output is correct |
10 |
Correct |
1 ms |
388 KB |
Output is correct |
11 |
Correct |
0 ms |
228 KB |
Output is correct |
12 |
Correct |
1 ms |
372 KB |
Output is correct |
13 |
Correct |
0 ms |
228 KB |
Output is correct |
14 |
Correct |
1 ms |
228 KB |
Output is correct |
15 |
Correct |
0 ms |
228 KB |
Output is correct |
16 |
Correct |
1 ms |
228 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Incorrect |
1 ms |
212 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1664 KB |
Output is correct |
2 |
Correct |
2 ms |
1580 KB |
Output is correct |
3 |
Correct |
1 ms |
388 KB |
Output is correct |
4 |
Correct |
0 ms |
228 KB |
Output is correct |
5 |
Correct |
1 ms |
372 KB |
Output is correct |
6 |
Correct |
0 ms |
228 KB |
Output is correct |
7 |
Correct |
1 ms |
228 KB |
Output is correct |
8 |
Correct |
0 ms |
228 KB |
Output is correct |
9 |
Correct |
1 ms |
228 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Incorrect |
1 ms |
212 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1308 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
224 KB |
Output is correct |
4 |
Correct |
2 ms |
1664 KB |
Output is correct |
5 |
Correct |
2 ms |
1580 KB |
Output is correct |
6 |
Correct |
1 ms |
1044 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
228 KB |
Output is correct |
9 |
Correct |
2 ms |
1536 KB |
Output is correct |
10 |
Correct |
1 ms |
388 KB |
Output is correct |
11 |
Correct |
0 ms |
228 KB |
Output is correct |
12 |
Correct |
1 ms |
372 KB |
Output is correct |
13 |
Correct |
0 ms |
228 KB |
Output is correct |
14 |
Correct |
1 ms |
228 KB |
Output is correct |
15 |
Correct |
0 ms |
228 KB |
Output is correct |
16 |
Correct |
1 ms |
228 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Incorrect |
1 ms |
212 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1664 KB |
Output is correct |
2 |
Correct |
2 ms |
1580 KB |
Output is correct |
3 |
Correct |
1 ms |
388 KB |
Output is correct |
4 |
Correct |
0 ms |
228 KB |
Output is correct |
5 |
Correct |
1 ms |
372 KB |
Output is correct |
6 |
Correct |
0 ms |
228 KB |
Output is correct |
7 |
Correct |
1 ms |
228 KB |
Output is correct |
8 |
Correct |
0 ms |
228 KB |
Output is correct |
9 |
Correct |
1 ms |
228 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Incorrect |
1 ms |
212 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1308 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
224 KB |
Output is correct |
4 |
Correct |
2 ms |
1664 KB |
Output is correct |
5 |
Correct |
2 ms |
1580 KB |
Output is correct |
6 |
Correct |
1 ms |
1044 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
228 KB |
Output is correct |
9 |
Correct |
2 ms |
1536 KB |
Output is correct |
10 |
Correct |
1 ms |
388 KB |
Output is correct |
11 |
Correct |
0 ms |
228 KB |
Output is correct |
12 |
Correct |
1 ms |
372 KB |
Output is correct |
13 |
Correct |
0 ms |
228 KB |
Output is correct |
14 |
Correct |
1 ms |
228 KB |
Output is correct |
15 |
Correct |
0 ms |
228 KB |
Output is correct |
16 |
Correct |
1 ms |
228 KB |
Output is correct |
17 |
Correct |
0 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
21 |
Incorrect |
1 ms |
212 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
22 |
Halted |
0 ms |
0 KB |
- |