// failed/subtask-smallN-wa1.cpp
#include "beechtree.h"
#include <set>
#include <algorithm>
using namespace std;
using pii = pair<int, int>;
int n, m;
vector<int> par;
vector<set<int>> ch_colors;
vector<int> t;
bool is_subset(int x, int y)
{
if (ch_colors[x].size() > ch_colors[y].size())
swap(x, y);
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 r = N - 1; r >= 0; --r)
{
solve(r);
}
return t;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
224 KB |
Output is correct |
2 |
Correct |
0 ms |
224 KB |
Output is correct |
3 |
Incorrect |
0 ms |
224 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
300 KB |
Output is correct |
2 |
Correct |
0 ms |
224 KB |
Output is correct |
3 |
Correct |
1 ms |
224 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
228 KB |
Output is correct |
6 |
Correct |
1 ms |
224 KB |
Output is correct |
7 |
Correct |
1 ms |
224 KB |
Output is correct |
8 |
Correct |
1 ms |
224 KB |
Output is correct |
9 |
Incorrect |
1 ms |
224 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
300 KB |
Output is correct |
2 |
Correct |
0 ms |
224 KB |
Output is correct |
3 |
Correct |
1 ms |
224 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
228 KB |
Output is correct |
6 |
Correct |
1 ms |
224 KB |
Output is correct |
7 |
Correct |
82 ms |
25132 KB |
Output is correct |
8 |
Correct |
69 ms |
27036 KB |
Output is correct |
9 |
Correct |
9 ms |
296 KB |
Output is correct |
10 |
Correct |
1 ms |
304 KB |
Output is correct |
11 |
Correct |
1 ms |
228 KB |
Output is correct |
12 |
Correct |
1 ms |
276 KB |
Output is correct |
13 |
Execution timed out |
2043 ms |
536 KB |
Time limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
216 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 |
1 ms |
224 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Incorrect |
1 ms |
212 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
300 KB |
Output is correct |
2 |
Correct |
0 ms |
224 KB |
Output is correct |
3 |
Correct |
1 ms |
224 KB |
Output is correct |
4 |
Correct |
1 ms |
224 KB |
Output is correct |
5 |
Correct |
82 ms |
25132 KB |
Output is correct |
6 |
Correct |
69 ms |
27036 KB |
Output is correct |
7 |
Correct |
1 ms |
216 KB |
Output is correct |
8 |
Correct |
1 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 |
2072 ms |
25428 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
224 KB |
Output is correct |
2 |
Correct |
0 ms |
224 KB |
Output is correct |
3 |
Incorrect |
0 ms |
224 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
300 KB |
Output is correct |
2 |
Correct |
0 ms |
224 KB |
Output is correct |
3 |
Correct |
1 ms |
224 KB |
Output is correct |
4 |
Correct |
1 ms |
224 KB |
Output is correct |
5 |
Incorrect |
1 ms |
224 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
224 KB |
Output is correct |
2 |
Correct |
0 ms |
224 KB |
Output is correct |
3 |
Incorrect |
0 ms |
224 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
300 KB |
Output is correct |
2 |
Correct |
0 ms |
224 KB |
Output is correct |
3 |
Correct |
1 ms |
224 KB |
Output is correct |
4 |
Correct |
1 ms |
224 KB |
Output is correct |
5 |
Incorrect |
1 ms |
224 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
224 KB |
Output is correct |
2 |
Correct |
0 ms |
224 KB |
Output is correct |
3 |
Incorrect |
0 ms |
224 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
4 |
Halted |
0 ms |
0 KB |
- |