#include "beechtree.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
const int N = 300500, inf = 1e9, mod = 998244353;
const ll INF = 1e18;
vector<pii> g[N];
int n, m;
int ans[N];
int P[N], C[N];
int tin[N], timer;
vector<int> t[N];
int sz[N];
map<int, int> was[N], dp[N];
bool f(int v, int u) {
if (was[v][u])
return dp[v][u];
was[v][u] = 1;
for (int i = 0, j = 0; i < g[u].size(); i++) {
while (j < g[v].size() && g[v][j].f != g[u][i].f)
j++;
if (j == g[v].size())
return dp[v][u] = false;
if (!f(g[v][j].s, g[u][i].s))
return dp[v][u] = false;
}
return dp[v][u] = true;
}
void dfs(int v) {
tin[v] = timer++;
sz[v] = 1;
ans[v] = 1;
vector<int> a;
for (int i = 0; i + 1 < g[v].size(); i++)
ans[v] &= (g[v][i].f != g[v][i + 1].f);
for (auto it: g[v]) {
int to = it.s;
a.pb(to);
dfs(to);
sz[v] += sz[to];
ans[v] &= ans[to];
ans[v] &= f(v, to);
}
sort(a.begin(), a.end(), [](int i, int j) {
return sz[i] > sz[j];
});
for (int i = 0; i + 1 < a.size(); i++)
ans[v] &= f(a[i], a[i + 1]);
}
vector<int> beechtree(int N, int M, vector<int> PP, vector<int> CC) {
n = N;
for (int i = 0; i < n; i++) {
g[i].clear();
P[i] = PP[i];
C[i] = CC[i];
ans[i] = 0;
was[i].clear();
dp[i].clear();
}
for (int i = 1; i < n; i++)
g[P[i]].pb({C[i], i});
for (int i = 0; i < n; i++)
sort(g[i].begin(), g[i].end());
dfs(0);
return vector<int>(ans, ans + n);
}
Compilation message
beechtree.cpp: In function 'bool first(int, int)':
beechtree.cpp:34:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for (int i = 0, j = 0; i < g[u].size(); i++) {
| ~~^~~~~~~~~~~~~
beechtree.cpp:35:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | while (j < g[v].size() && g[v][j].f != g[u][i].f)
| ~~^~~~~~~~~~~~~
beechtree.cpp:37:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | if (j == g[v].size())
| ~~^~~~~~~~~~~~~~
beechtree.cpp:38:29: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
38 | return dp[v][u] = false;
beechtree.cpp:40:29: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
40 | return dp[v][u] = false;
beechtree.cpp:42:21: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
42 | return dp[v][u] = true;
beechtree.cpp: In function 'void dfs(int)':
beechtree.cpp:50:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (int i = 0; i + 1 < g[v].size(); i++)
| ~~~~~~^~~~~~~~~~~~~
beechtree.cpp:63:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for (int i = 0; i + 1 < a.size(); i++)
| ~~~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
48472 KB |
Output is correct |
2 |
Correct |
9 ms |
48476 KB |
Output is correct |
3 |
Correct |
9 ms |
48452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
48476 KB |
Output is correct |
2 |
Correct |
9 ms |
48476 KB |
Output is correct |
3 |
Correct |
10 ms |
48476 KB |
Output is correct |
4 |
Correct |
9 ms |
48472 KB |
Output is correct |
5 |
Correct |
9 ms |
48476 KB |
Output is correct |
6 |
Correct |
9 ms |
48476 KB |
Output is correct |
7 |
Correct |
9 ms |
48428 KB |
Output is correct |
8 |
Correct |
10 ms |
48476 KB |
Output is correct |
9 |
Correct |
9 ms |
48568 KB |
Output is correct |
10 |
Correct |
9 ms |
48640 KB |
Output is correct |
11 |
Correct |
10 ms |
48476 KB |
Output is correct |
12 |
Correct |
10 ms |
48476 KB |
Output is correct |
13 |
Correct |
10 ms |
48632 KB |
Output is correct |
14 |
Incorrect |
9 ms |
48476 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 |
9 ms |
48476 KB |
Output is correct |
2 |
Correct |
9 ms |
48476 KB |
Output is correct |
3 |
Correct |
10 ms |
48476 KB |
Output is correct |
4 |
Correct |
9 ms |
48472 KB |
Output is correct |
5 |
Correct |
9 ms |
48476 KB |
Output is correct |
6 |
Correct |
9 ms |
48476 KB |
Output is correct |
7 |
Correct |
118 ms |
102436 KB |
Output is correct |
8 |
Correct |
112 ms |
102440 KB |
Output is correct |
9 |
Correct |
9 ms |
48476 KB |
Output is correct |
10 |
Correct |
9 ms |
48476 KB |
Output is correct |
11 |
Correct |
9 ms |
48668 KB |
Output is correct |
12 |
Correct |
9 ms |
48476 KB |
Output is correct |
13 |
Correct |
10 ms |
49208 KB |
Output is correct |
14 |
Correct |
11 ms |
48988 KB |
Output is correct |
15 |
Correct |
10 ms |
48988 KB |
Output is correct |
16 |
Correct |
10 ms |
49184 KB |
Output is correct |
17 |
Correct |
111 ms |
102432 KB |
Output is correct |
18 |
Correct |
114 ms |
104992 KB |
Output is correct |
19 |
Correct |
111 ms |
105044 KB |
Output is correct |
20 |
Correct |
117 ms |
105044 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
48472 KB |
Output is correct |
2 |
Correct |
9 ms |
48476 KB |
Output is correct |
3 |
Correct |
9 ms |
48528 KB |
Output is correct |
4 |
Correct |
9 ms |
48472 KB |
Output is correct |
5 |
Correct |
10 ms |
48828 KB |
Output is correct |
6 |
Correct |
9 ms |
48476 KB |
Output is correct |
7 |
Correct |
9 ms |
48668 KB |
Output is correct |
8 |
Correct |
9 ms |
48476 KB |
Output is correct |
9 |
Correct |
9 ms |
48672 KB |
Output is correct |
10 |
Correct |
9 ms |
48476 KB |
Output is correct |
11 |
Correct |
11 ms |
48988 KB |
Output is correct |
12 |
Correct |
10 ms |
48728 KB |
Output is correct |
13 |
Correct |
11 ms |
48988 KB |
Output is correct |
14 |
Correct |
10 ms |
48988 KB |
Output is correct |
15 |
Correct |
215 ms |
90596 KB |
Output is correct |
16 |
Correct |
195 ms |
85960 KB |
Output is correct |
17 |
Correct |
204 ms |
88400 KB |
Output is correct |
18 |
Correct |
212 ms |
89904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
48476 KB |
Output is correct |
2 |
Correct |
9 ms |
48476 KB |
Output is correct |
3 |
Correct |
9 ms |
48428 KB |
Output is correct |
4 |
Correct |
10 ms |
48476 KB |
Output is correct |
5 |
Correct |
118 ms |
102436 KB |
Output is correct |
6 |
Correct |
112 ms |
102440 KB |
Output is correct |
7 |
Correct |
10 ms |
48472 KB |
Output is correct |
8 |
Correct |
9 ms |
48472 KB |
Output is correct |
9 |
Correct |
11 ms |
48984 KB |
Output is correct |
10 |
Correct |
11 ms |
48988 KB |
Output is correct |
11 |
Correct |
153 ms |
94432 KB |
Output is correct |
12 |
Correct |
279 ms |
93264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
48472 KB |
Output is correct |
2 |
Correct |
9 ms |
48476 KB |
Output is correct |
3 |
Correct |
9 ms |
48452 KB |
Output is correct |
4 |
Correct |
9 ms |
48476 KB |
Output is correct |
5 |
Correct |
9 ms |
48476 KB |
Output is correct |
6 |
Correct |
10 ms |
48476 KB |
Output is correct |
7 |
Correct |
9 ms |
48472 KB |
Output is correct |
8 |
Correct |
9 ms |
48476 KB |
Output is correct |
9 |
Correct |
9 ms |
48476 KB |
Output is correct |
10 |
Correct |
9 ms |
48428 KB |
Output is correct |
11 |
Correct |
10 ms |
48476 KB |
Output is correct |
12 |
Correct |
9 ms |
48568 KB |
Output is correct |
13 |
Correct |
9 ms |
48640 KB |
Output is correct |
14 |
Correct |
10 ms |
48476 KB |
Output is correct |
15 |
Correct |
10 ms |
48476 KB |
Output is correct |
16 |
Correct |
10 ms |
48632 KB |
Output is correct |
17 |
Incorrect |
9 ms |
48476 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 |
9 ms |
48476 KB |
Output is correct |
2 |
Correct |
9 ms |
48476 KB |
Output is correct |
3 |
Correct |
9 ms |
48428 KB |
Output is correct |
4 |
Correct |
10 ms |
48476 KB |
Output is correct |
5 |
Correct |
9 ms |
48568 KB |
Output is correct |
6 |
Correct |
9 ms |
48640 KB |
Output is correct |
7 |
Correct |
10 ms |
48476 KB |
Output is correct |
8 |
Correct |
10 ms |
48476 KB |
Output is correct |
9 |
Correct |
10 ms |
48632 KB |
Output is correct |
10 |
Incorrect |
9 ms |
48476 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 |
9 ms |
48472 KB |
Output is correct |
2 |
Correct |
9 ms |
48476 KB |
Output is correct |
3 |
Correct |
9 ms |
48452 KB |
Output is correct |
4 |
Correct |
9 ms |
48476 KB |
Output is correct |
5 |
Correct |
9 ms |
48476 KB |
Output is correct |
6 |
Correct |
10 ms |
48476 KB |
Output is correct |
7 |
Correct |
9 ms |
48472 KB |
Output is correct |
8 |
Correct |
9 ms |
48476 KB |
Output is correct |
9 |
Correct |
9 ms |
48476 KB |
Output is correct |
10 |
Correct |
9 ms |
48428 KB |
Output is correct |
11 |
Correct |
10 ms |
48476 KB |
Output is correct |
12 |
Correct |
9 ms |
48568 KB |
Output is correct |
13 |
Correct |
9 ms |
48640 KB |
Output is correct |
14 |
Correct |
10 ms |
48476 KB |
Output is correct |
15 |
Correct |
10 ms |
48476 KB |
Output is correct |
16 |
Correct |
10 ms |
48632 KB |
Output is correct |
17 |
Incorrect |
9 ms |
48476 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 |
9 ms |
48476 KB |
Output is correct |
2 |
Correct |
9 ms |
48476 KB |
Output is correct |
3 |
Correct |
9 ms |
48428 KB |
Output is correct |
4 |
Correct |
10 ms |
48476 KB |
Output is correct |
5 |
Correct |
9 ms |
48568 KB |
Output is correct |
6 |
Correct |
9 ms |
48640 KB |
Output is correct |
7 |
Correct |
10 ms |
48476 KB |
Output is correct |
8 |
Correct |
10 ms |
48476 KB |
Output is correct |
9 |
Correct |
10 ms |
48632 KB |
Output is correct |
10 |
Incorrect |
9 ms |
48476 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 |
9 ms |
48472 KB |
Output is correct |
2 |
Correct |
9 ms |
48476 KB |
Output is correct |
3 |
Correct |
9 ms |
48452 KB |
Output is correct |
4 |
Correct |
9 ms |
48476 KB |
Output is correct |
5 |
Correct |
9 ms |
48476 KB |
Output is correct |
6 |
Correct |
10 ms |
48476 KB |
Output is correct |
7 |
Correct |
9 ms |
48472 KB |
Output is correct |
8 |
Correct |
9 ms |
48476 KB |
Output is correct |
9 |
Correct |
9 ms |
48476 KB |
Output is correct |
10 |
Correct |
9 ms |
48428 KB |
Output is correct |
11 |
Correct |
10 ms |
48476 KB |
Output is correct |
12 |
Correct |
9 ms |
48568 KB |
Output is correct |
13 |
Correct |
9 ms |
48640 KB |
Output is correct |
14 |
Correct |
10 ms |
48476 KB |
Output is correct |
15 |
Correct |
10 ms |
48476 KB |
Output is correct |
16 |
Correct |
10 ms |
48632 KB |
Output is correct |
17 |
Incorrect |
9 ms |
48476 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
18 |
Halted |
0 ms |
0 KB |
- |