// incorrect/solution-amshz-wa.cpp
#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define F first
#define S second
const int xn = 2e5 + 10;
int n, m, par[xn], a[xn], sz[xn];
pii dsu[xn];
vector<int> adj[xn];
set<pii> st[xn], chil[xn];
bool ans[xn], ns[xn];
map<int, int> mp[xn];
bool is_ok(int v, int u)
{
for (int x : adj[v])
if (mp[u][a[x]] < sz[x])
return false;
return true;
}
int get_root(int v)
{
if (v == dsu[v].F)
return v;
return dsu[v].F = get_root(dsu[v].F);
}
void merge(int v, int u)
{
v = get_root(v);
u = get_root(u);
if (dsu[v].S < dsu[u].S)
swap(v, u);
dsu[u].F = v;
dsu[v].S += dsu[u].S;
if (!ns[v] || !ns[u])
{
ns[v] = false;
return;
}
for (pii x : st[u])
{
st[v].insert(x);
auto it = st[v].find(x);
it++;
if (it != st[v].end())
{
int next_ver = it->S;
if (!is_ok(x.S, next_ver))
{
ns[v] = false;
break;
}
}
it--;
if (it != st[v].begin())
{
it--;
int prev_ver = it->S;
if (!is_ok(prev_ver, x.S))
{
ns[v] = false;
break;
}
}
st[v].insert(x);
}
}
void DFS(int v)
{
sz[v] = 1;
for (int u : adj[v])
{
DFS(u);
sz[v] += sz[u];
mp[v][a[u]] = sz[u];
}
st[v].insert({sz[v], v});
dsu[v] = {v, 1};
ns[v] = true;
for (int u : adj[v])
merge(v, u);
ans[v] = ns[get_root(v)];
}
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C)
{
n = N - 1, m = M;
for (int i = 1; i <= n; ++i)
{
par[i] = P[i], a[i] = C[i];
adj[par[i]].push_back(i);
}
DFS(0);
vector<int> ret(N);
for (int i = 0; i <= n; ++i)
ret[i] = ans[i];
return ret;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
23 ms |
33124 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
33208 KB |
Output is correct |
2 |
Correct |
20 ms |
33192 KB |
Output is correct |
3 |
Correct |
31 ms |
33144 KB |
Output is correct |
4 |
Correct |
17 ms |
33120 KB |
Output is correct |
5 |
Correct |
22 ms |
34192 KB |
Output is correct |
6 |
Correct |
21 ms |
33120 KB |
Output is correct |
7 |
Incorrect |
19 ms |
34320 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
33208 KB |
Output is correct |
2 |
Correct |
20 ms |
33192 KB |
Output is correct |
3 |
Correct |
31 ms |
33144 KB |
Output is correct |
4 |
Correct |
17 ms |
33120 KB |
Output is correct |
5 |
Correct |
22 ms |
34192 KB |
Output is correct |
6 |
Correct |
21 ms |
33120 KB |
Output is correct |
7 |
Correct |
196 ms |
93312 KB |
Output is correct |
8 |
Correct |
146 ms |
93920 KB |
Output is correct |
9 |
Correct |
22 ms |
33208 KB |
Output is correct |
10 |
Correct |
20 ms |
33364 KB |
Output is correct |
11 |
Correct |
19 ms |
33388 KB |
Output is correct |
12 |
Correct |
63 ms |
34044 KB |
Output is correct |
13 |
Correct |
25 ms |
34044 KB |
Output is correct |
14 |
Correct |
33 ms |
34364 KB |
Output is correct |
15 |
Correct |
19 ms |
33812 KB |
Output is correct |
16 |
Correct |
24 ms |
33708 KB |
Output is correct |
17 |
Correct |
281 ms |
101996 KB |
Output is correct |
18 |
Correct |
276 ms |
98088 KB |
Output is correct |
19 |
Correct |
200 ms |
93664 KB |
Output is correct |
20 |
Correct |
353 ms |
91816 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
112 ms |
33280 KB |
Output is correct |
2 |
Incorrect |
19 ms |
33244 KB |
2nd lines differ - on the 4th token, expected: '0', found: '1' |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
33208 KB |
Output is correct |
2 |
Correct |
20 ms |
33192 KB |
Output is correct |
3 |
Incorrect |
19 ms |
34320 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
23 ms |
33124 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
33208 KB |
Output is correct |
2 |
Correct |
20 ms |
33192 KB |
Output is correct |
3 |
Incorrect |
19 ms |
34320 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
23 ms |
33124 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
33208 KB |
Output is correct |
2 |
Correct |
20 ms |
33192 KB |
Output is correct |
3 |
Incorrect |
19 ms |
34320 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
23 ms |
33124 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
2 |
Halted |
0 ms |
0 KB |
- |