// incorrect/sol_na_wa5.cpp
#include "beechtree.h"
#include <algorithm>
#include <iostream>
#include <map>
#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
std::vector<std::vector<std::pair<int, int>>> adj;
struct data
{
bool ok = true;
int sz = 0;
std::map<int, int> cnt;
data() {}
data(int ind)
{
for (auto i : adj[ind])
{
sz++;
cnt[i.yy]++;
ok &= cnt[i.yy] == 1;
}
}
void check(const data &masik, bool root = false)
{
int sum = 0;
for (auto i : masik.cnt)
{
if (!root)
{
ok &= i.yy <= cnt[i.xx];
if (cnt[i.xx] > 1)
ok &= i.yy > 0;
}
else
{
sum += cnt[i.xx];
}
}
if (root)
ok &= sum == sz;
}
void add(const data &masik, bool root = false)
{
ok &= masik.ok;
for (auto i : masik.cnt)
{
cnt[i.xx] += i.yy;
}
sz += masik.sz;
}
};
std::vector<int> ans;
data *dfs(int x)
{
if (adj[x].size() == 0)
{
ans[x] = 1;
return new data();
}
std::vector<data *> lst;
for (auto i : adj[x])
{
lst.push_back(dfs(i.first));
}
sort(lst.begin(), lst.end(), [&](data *a, data *b) -> bool
{ return a->sz < b->sz; });
for (int i = 1; i < (int)lst.size(); ++i)
{
lst[i]->check(*lst[i - 1]);
}
data *curr = new data(x);
lst.back()->check(*curr, true);
for (int i = 1; i < (int)lst.size(); ++i)
{
lst.back()->add(*lst[i - 1]);
delete lst[i - 1];
}
lst.back()->add(*curr, true);
delete curr;
ans[x] = lst.back()->ok;
return lst.back();
}
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
adj.resize(N);
for (int i = 1; i < N; ++i)
{
adj[P[i]].push_back({i, C[i]});
// adj[i].push_back({P[i], C[i]});
}
ans.resize(N);
dfs(0);
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 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 |
1 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 |
304 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
300 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
304 KB |
Output is correct |
12 |
Correct |
0 ms |
308 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Incorrect |
1 ms |
340 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 |
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 |
1 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 |
180 ms |
66104 KB |
Output is correct |
8 |
Correct |
144 ms |
63756 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
828 KB |
Output is correct |
14 |
Correct |
2 ms |
852 KB |
Output is correct |
15 |
Correct |
2 ms |
852 KB |
Output is correct |
16 |
Correct |
2 ms |
844 KB |
Output is correct |
17 |
Correct |
86 ms |
58896 KB |
Output is correct |
18 |
Correct |
91 ms |
59068 KB |
Output is correct |
19 |
Correct |
129 ms |
63348 KB |
Output is correct |
20 |
Correct |
158 ms |
65056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
224 KB |
Output is correct |
2 |
Correct |
1 ms |
220 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
300 KB |
Output is correct |
6 |
Correct |
1 ms |
220 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
268 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
352 KB |
Output is correct |
15 |
Correct |
95 ms |
11888 KB |
Output is correct |
16 |
Correct |
70 ms |
11208 KB |
Output is correct |
17 |
Correct |
92 ms |
11284 KB |
Output is correct |
18 |
Correct |
73 ms |
11724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
304 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
180 ms |
66104 KB |
Output is correct |
6 |
Correct |
144 ms |
63756 KB |
Output is correct |
7 |
Correct |
1 ms |
304 KB |
Output is correct |
8 |
Correct |
1 ms |
316 KB |
Output is correct |
9 |
Correct |
2 ms |
472 KB |
Output is correct |
10 |
Correct |
3 ms |
452 KB |
Output is correct |
11 |
Correct |
154 ms |
24980 KB |
Output is correct |
12 |
Correct |
173 ms |
19580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
304 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
300 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
304 KB |
Output is correct |
15 |
Correct |
0 ms |
308 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Incorrect |
1 ms |
340 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
304 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
300 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
304 KB |
Output is correct |
8 |
Correct |
0 ms |
308 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Incorrect |
1 ms |
340 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
304 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
300 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
304 KB |
Output is correct |
15 |
Correct |
0 ms |
308 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Incorrect |
1 ms |
340 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
18 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
304 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
300 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
304 KB |
Output is correct |
8 |
Correct |
0 ms |
308 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Incorrect |
1 ms |
340 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
304 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
300 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
304 KB |
Output is correct |
15 |
Correct |
0 ms |
308 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Incorrect |
1 ms |
340 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
18 |
Halted |
0 ms |
0 KB |
- |