// incorrect/sol_na_wa2.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 add(const data &masik, bool root = false)
{
ok &= masik.ok;
int sum = 0;
for (auto i : masik.cnt)
{
if (!root)
ok &= i.yy <= cnt[i.xx];
else
{
sum += cnt[i.xx];
}
cnt[i.xx] += i.yy;
}
if (root)
ok &= sum == sz;
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.back()->add(*lst[i - 1]);
delete lst[i - 1];
}
data *curr = new data(x);
lst.back()->add(*curr, true);
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 |
308 KB |
Output is correct |
2 |
Correct |
1 ms |
216 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
304 KB |
Output is correct |
2 |
Correct |
1 ms |
216 KB |
Output is correct |
3 |
Correct |
1 ms |
216 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 |
296 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
304 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
296 KB |
Output is correct |
11 |
Correct |
1 ms |
296 KB |
Output is correct |
12 |
Correct |
1 ms |
304 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 |
304 KB |
Output is correct |
2 |
Correct |
1 ms |
216 KB |
Output is correct |
3 |
Correct |
1 ms |
216 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 |
296 KB |
Output is correct |
7 |
Correct |
393 ms |
86968 KB |
Output is correct |
8 |
Correct |
209 ms |
84644 KB |
Output is correct |
9 |
Correct |
1 ms |
352 KB |
Output is correct |
10 |
Correct |
1 ms |
352 KB |
Output is correct |
11 |
Correct |
1 ms |
296 KB |
Output is correct |
12 |
Correct |
1 ms |
304 KB |
Output is correct |
13 |
Correct |
2 ms |
1084 KB |
Output is correct |
14 |
Correct |
2 ms |
980 KB |
Output is correct |
15 |
Correct |
2 ms |
1076 KB |
Output is correct |
16 |
Correct |
2 ms |
1112 KB |
Output is correct |
17 |
Correct |
139 ms |
79580 KB |
Output is correct |
18 |
Correct |
247 ms |
80216 KB |
Output is correct |
19 |
Correct |
193 ms |
84700 KB |
Output is correct |
20 |
Correct |
233 ms |
86928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
316 KB |
Output is correct |
2 |
Correct |
1 ms |
228 KB |
Output is correct |
3 |
Incorrect |
1 ms |
220 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 |
304 KB |
Output is correct |
2 |
Correct |
1 ms |
216 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
393 ms |
86968 KB |
Output is correct |
6 |
Correct |
209 ms |
84644 KB |
Output is correct |
7 |
Correct |
1 ms |
224 KB |
Output is correct |
8 |
Correct |
1 ms |
320 KB |
Output is correct |
9 |
Correct |
2 ms |
608 KB |
Output is correct |
10 |
Correct |
2 ms |
480 KB |
Output is correct |
11 |
Correct |
185 ms |
35968 KB |
Output is correct |
12 |
Correct |
162 ms |
27896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
308 KB |
Output is correct |
2 |
Correct |
1 ms |
216 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
216 KB |
Output is correct |
6 |
Correct |
1 ms |
216 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
300 KB |
Output is correct |
9 |
Correct |
1 ms |
296 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
304 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
296 KB |
Output is correct |
14 |
Correct |
1 ms |
296 KB |
Output is correct |
15 |
Correct |
1 ms |
304 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Incorrect |
1 ms |
212 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 |
304 KB |
Output is correct |
2 |
Correct |
1 ms |
216 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
296 KB |
Output is correct |
7 |
Correct |
1 ms |
296 KB |
Output is correct |
8 |
Correct |
1 ms |
304 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Incorrect |
1 ms |
212 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 |
308 KB |
Output is correct |
2 |
Correct |
1 ms |
216 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
216 KB |
Output is correct |
6 |
Correct |
1 ms |
216 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
300 KB |
Output is correct |
9 |
Correct |
1 ms |
296 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
304 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
296 KB |
Output is correct |
14 |
Correct |
1 ms |
296 KB |
Output is correct |
15 |
Correct |
1 ms |
304 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Incorrect |
1 ms |
212 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 |
304 KB |
Output is correct |
2 |
Correct |
1 ms |
216 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
296 KB |
Output is correct |
7 |
Correct |
1 ms |
296 KB |
Output is correct |
8 |
Correct |
1 ms |
304 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Incorrect |
1 ms |
212 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 |
308 KB |
Output is correct |
2 |
Correct |
1 ms |
216 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
216 KB |
Output is correct |
6 |
Correct |
1 ms |
216 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
300 KB |
Output is correct |
9 |
Correct |
1 ms |
296 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
304 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
296 KB |
Output is correct |
14 |
Correct |
1 ms |
296 KB |
Output is correct |
15 |
Correct |
1 ms |
304 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Incorrect |
1 ms |
212 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
18 |
Halted |
0 ms |
0 KB |
- |