// incorrect/solution-keshi-wa.cpp
// In the name of God
#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 100;
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
int n, m;
int a[maxn], p[maxn], sz[maxn];
vector<pii> g[maxn];
map<int, int> gsz[maxn];
set<pii> st[maxn];
bool ok[maxn];
void dfs(int v)
{
sz[v] = 1;
for (pii u : g[v])
{
dfs(u.F);
sz[v] += sz[u.F];
if (gsz[v].count(u.S))
ok[v] = false;
gsz[v][u.S] = sz[u.F];
}
return;
}
bool check(int v, int u)
{
if (Sz(gsz[v]) > Sz(gsz[u]))
return 0;
for (pii i : gsz[v])
{
auto it = gsz[u].find(i.F);
if (it == gsz[u].end() && i.S > it->S)
return 0;
}
return 1;
}
bool add(int x, pii o)
{
st[x].insert(o);
auto it = st[x].find(o);
if (it != st[x].begin())
{
auto it2 = it;
it2--;
if (!check(it2->S, o.S))
return 0;
}
it++;
if (it != st[x].end())
{
if (!check(o.S, it->S))
return 0;
}
return 1;
}
void solve(int v)
{
st[v].insert(Mp(sz[v], v));
for (pii uu : g[v])
{
int u = uu.F;
solve(u);
ok[v] &= ok[u];
if (Sz(st[v]) < Sz(st[u]))
st[v].swap(st[u]);
for (pii i : st[u])
{
ok[v] &= add(v, i);
}
}
return;
}
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C)
{
/*
p[i] : parent of node i
a[i] : the color of the edge between node i and p[i]
sz[i] : the size of the subtree of node i
g[i] : vector of <child, color>
gsz[i] : map of <color, sz of child with that color>
st[i] : set of <sz, node>
*/
n = N - 1, m = M;
for (int i = 1; i <= n; i++)
{
p[i] = P[i], a[i] = C[i];
g[p[i]].pb(Mp(i, a[i]));
}
fill(ok, ok + n + 10, 1);
dfs(0);
solve(0);
vector<int> ans(N);
for (int i = 0; i <= n; i++)
{
ans[i] = ok[i];
}
return ans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
23748 KB |
Output is correct |
2 |
Correct |
13 ms |
23708 KB |
Output is correct |
3 |
Correct |
15 ms |
23780 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
23776 KB |
Output is correct |
2 |
Correct |
11 ms |
23776 KB |
Output is correct |
3 |
Correct |
16 ms |
23768 KB |
Output is correct |
4 |
Correct |
12 ms |
23904 KB |
Output is correct |
5 |
Correct |
10 ms |
23784 KB |
Output is correct |
6 |
Correct |
12 ms |
23832 KB |
Output is correct |
7 |
Correct |
16 ms |
23816 KB |
Output is correct |
8 |
Correct |
11 ms |
23760 KB |
Output is correct |
9 |
Incorrect |
12 ms |
23720 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
23776 KB |
Output is correct |
2 |
Correct |
11 ms |
23776 KB |
Output is correct |
3 |
Correct |
16 ms |
23768 KB |
Output is correct |
4 |
Correct |
12 ms |
23904 KB |
Output is correct |
5 |
Correct |
10 ms |
23784 KB |
Output is correct |
6 |
Correct |
12 ms |
23832 KB |
Output is correct |
7 |
Correct |
188 ms |
89032 KB |
Output is correct |
8 |
Correct |
173 ms |
89100 KB |
Output is correct |
9 |
Correct |
14 ms |
23872 KB |
Output is correct |
10 |
Correct |
12 ms |
23764 KB |
Output is correct |
11 |
Correct |
12 ms |
23816 KB |
Output is correct |
12 |
Correct |
12 ms |
23892 KB |
Output is correct |
13 |
Correct |
11 ms |
24436 KB |
Output is correct |
14 |
Correct |
11 ms |
24464 KB |
Output is correct |
15 |
Correct |
14 ms |
24464 KB |
Output is correct |
16 |
Correct |
15 ms |
24440 KB |
Output is correct |
17 |
Correct |
202 ms |
88788 KB |
Output is correct |
18 |
Correct |
177 ms |
88996 KB |
Output is correct |
19 |
Correct |
196 ms |
89092 KB |
Output is correct |
20 |
Correct |
214 ms |
89032 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
18 ms |
23828 KB |
Output is correct |
2 |
Correct |
14 ms |
23856 KB |
Output is correct |
3 |
Correct |
13 ms |
23816 KB |
Output is correct |
4 |
Correct |
14 ms |
23792 KB |
Output is correct |
5 |
Correct |
13 ms |
23808 KB |
Output is correct |
6 |
Correct |
10 ms |
23740 KB |
Output is correct |
7 |
Correct |
13 ms |
23796 KB |
Output is correct |
8 |
Correct |
10 ms |
23820 KB |
Output is correct |
9 |
Correct |
10 ms |
23816 KB |
Output is correct |
10 |
Correct |
12 ms |
23764 KB |
Output is correct |
11 |
Correct |
12 ms |
24020 KB |
Output is correct |
12 |
Correct |
14 ms |
23948 KB |
Output is correct |
13 |
Correct |
12 ms |
24064 KB |
Output is correct |
14 |
Correct |
11 ms |
24032 KB |
Output is correct |
15 |
Correct |
120 ms |
48732 KB |
Output is correct |
16 |
Correct |
150 ms |
47304 KB |
Output is correct |
17 |
Correct |
128 ms |
47512 KB |
Output is correct |
18 |
Correct |
131 ms |
48376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
23776 KB |
Output is correct |
2 |
Correct |
11 ms |
23776 KB |
Output is correct |
3 |
Correct |
16 ms |
23816 KB |
Output is correct |
4 |
Correct |
11 ms |
23760 KB |
Output is correct |
5 |
Correct |
188 ms |
89032 KB |
Output is correct |
6 |
Correct |
173 ms |
89100 KB |
Output is correct |
7 |
Correct |
13 ms |
23816 KB |
Output is correct |
8 |
Correct |
12 ms |
23772 KB |
Output is correct |
9 |
Correct |
17 ms |
24260 KB |
Output is correct |
10 |
Correct |
19 ms |
24248 KB |
Output is correct |
11 |
Correct |
233 ms |
74688 KB |
Output is correct |
12 |
Correct |
257 ms |
69224 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
23748 KB |
Output is correct |
2 |
Correct |
13 ms |
23708 KB |
Output is correct |
3 |
Correct |
15 ms |
23780 KB |
Output is correct |
4 |
Correct |
11 ms |
23776 KB |
Output is correct |
5 |
Correct |
11 ms |
23776 KB |
Output is correct |
6 |
Correct |
16 ms |
23768 KB |
Output is correct |
7 |
Correct |
12 ms |
23904 KB |
Output is correct |
8 |
Correct |
10 ms |
23784 KB |
Output is correct |
9 |
Correct |
12 ms |
23832 KB |
Output is correct |
10 |
Correct |
16 ms |
23816 KB |
Output is correct |
11 |
Correct |
11 ms |
23760 KB |
Output is correct |
12 |
Incorrect |
12 ms |
23720 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
23776 KB |
Output is correct |
2 |
Correct |
11 ms |
23776 KB |
Output is correct |
3 |
Correct |
16 ms |
23816 KB |
Output is correct |
4 |
Correct |
11 ms |
23760 KB |
Output is correct |
5 |
Incorrect |
12 ms |
23720 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
23748 KB |
Output is correct |
2 |
Correct |
13 ms |
23708 KB |
Output is correct |
3 |
Correct |
15 ms |
23780 KB |
Output is correct |
4 |
Correct |
11 ms |
23776 KB |
Output is correct |
5 |
Correct |
11 ms |
23776 KB |
Output is correct |
6 |
Correct |
16 ms |
23768 KB |
Output is correct |
7 |
Correct |
12 ms |
23904 KB |
Output is correct |
8 |
Correct |
10 ms |
23784 KB |
Output is correct |
9 |
Correct |
12 ms |
23832 KB |
Output is correct |
10 |
Correct |
16 ms |
23816 KB |
Output is correct |
11 |
Correct |
11 ms |
23760 KB |
Output is correct |
12 |
Incorrect |
12 ms |
23720 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
23776 KB |
Output is correct |
2 |
Correct |
11 ms |
23776 KB |
Output is correct |
3 |
Correct |
16 ms |
23816 KB |
Output is correct |
4 |
Correct |
11 ms |
23760 KB |
Output is correct |
5 |
Incorrect |
12 ms |
23720 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
23748 KB |
Output is correct |
2 |
Correct |
13 ms |
23708 KB |
Output is correct |
3 |
Correct |
15 ms |
23780 KB |
Output is correct |
4 |
Correct |
11 ms |
23776 KB |
Output is correct |
5 |
Correct |
11 ms |
23776 KB |
Output is correct |
6 |
Correct |
16 ms |
23768 KB |
Output is correct |
7 |
Correct |
12 ms |
23904 KB |
Output is correct |
8 |
Correct |
10 ms |
23784 KB |
Output is correct |
9 |
Correct |
12 ms |
23832 KB |
Output is correct |
10 |
Correct |
16 ms |
23816 KB |
Output is correct |
11 |
Correct |
11 ms |
23760 KB |
Output is correct |
12 |
Incorrect |
12 ms |
23720 KB |
2nd lines differ - on the 1st token, expected: '0', found: '1' |
13 |
Halted |
0 ms |
0 KB |
- |