108322024-04-16 10:27:05TomaSajtVállalati ügyeletcpp17Runtime error 30/100714ms263016 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> g;
vector<set<int>> subtree_sets;
vector<int> val;
vector<int> mexes;

void dfs(int u) {
  int best_v = -1;
  for (int v : g[u]) {
    dfs(v);
    mexes[u] = max(mexes[u], mexes[v]);
    if (best_v == -1 || subtree_sets[v].size() > subtree_sets[best_v].size()) v = best_v;
  }
  if (best_v != -1) subtree_sets[u] = subtree_sets[best_v];
  subtree_sets[u].insert(val[u]);
  for (int v : g[u]) {
    if (v == best_v) continue;
    subtree_sets[u].insert(subtree_sets[v].begin(), subtree_sets[v].end());
  }
  auto it = subtree_sets[u].lower_bound(mexes[u]);
  while (it != subtree_sets[u].end() && *it == mexes[u]) mexes[u]++, it++;
}

signed main() {
  ios::sync_with_stdio(0), cin.tie(0);
  int n;
  cin >> n;
  g.resize(n + 1);
  subtree_sets.resize(n + 1);
  mexes.resize(n + 1, 1);
  val.resize(n + 1);
  for (int i = 1; i <= n; i++) {
    int p;
    cin >> p;
    g[p].push_back(i);
  }
  for (int i = 1; i <= n; i++) cin >> val[i];
  dfs(1);
  for (int i = 1; i <= n; i++) cout << mexes[i] << ' ';
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1760 KiB
2Runtime error372ms263016 KiB
subtask25/5
3Accepted3ms2160 KiB
4Accepted3ms2384 KiB
5Accepted3ms2464 KiB
6Accepted3ms2696 KiB
subtask38/8
7Accepted3ms2160 KiB
8Accepted3ms2384 KiB
9Accepted3ms2464 KiB
10Accepted3ms2696 KiB
11Accepted118ms59964 KiB
12Accepted120ms60928 KiB
13Accepted126ms62152 KiB
14Accepted186ms78292 KiB
subtask40/12
15Accepted3ms2160 KiB
16Accepted3ms2384 KiB
17Accepted3ms2464 KiB
18Accepted3ms2696 KiB
19Runtime error284ms261536 KiB
20Runtime error286ms261424 KiB
21Runtime error287ms261416 KiB
22Runtime error289ms261400 KiB
23Runtime error330ms261388 KiB
24Runtime error321ms261160 KiB
subtask517/17
25Accepted3ms2160 KiB
26Accepted3ms2384 KiB
27Accepted3ms2464 KiB
28Accepted3ms2696 KiB
29Accepted4ms4644 KiB
30Accepted314ms192440 KiB
31Accepted356ms192444 KiB
32Accepted46ms27508 KiB
33Accepted137ms75868 KiB
34Accepted4ms4848 KiB
35Accepted6ms5828 KiB
36Accepted32ms21520 KiB
37Accepted182ms113848 KiB
38Accepted10ms9424 KiB
39Accepted17ms13708 KiB
40Accepted13ms10340 KiB
41Accepted70ms41964 KiB
subtask60/28
42Runtime error453ms260828 KiB
43Runtime error389ms260820 KiB
44Runtime error370ms260804 KiB
45Runtime error354ms260800 KiB
46Runtime error342ms260792 KiB
47Runtime error333ms260796 KiB
48Accepted199ms79436 KiB
49Runtime error287ms260560 KiB
50Runtime error328ms260560 KiB
subtask70/30
51Accepted3ms4480 KiB
52Runtime error360ms260536 KiB
53Accepted3ms2160 KiB
54Accepted3ms2384 KiB
55Accepted3ms2464 KiB
56Accepted3ms2696 KiB
57Accepted118ms59964 KiB
58Accepted120ms60928 KiB
59Accepted126ms62152 KiB
60Accepted186ms78292 KiB
61Runtime error284ms261536 KiB
62Runtime error286ms261424 KiB
63Runtime error287ms261416 KiB
64Runtime error289ms261400 KiB
65Runtime error330ms261388 KiB
66Runtime error321ms261160 KiB
67Accepted4ms4644 KiB
68Accepted314ms192440 KiB
69Accepted356ms192444 KiB
70Accepted46ms27508 KiB
71Accepted137ms75868 KiB
72Accepted4ms4848 KiB
73Accepted6ms5828 KiB
74Accepted32ms21520 KiB
75Accepted182ms113848 KiB
76Accepted10ms9424 KiB
77Accepted17ms13708 KiB
78Accepted13ms10340 KiB
79Accepted70ms41964 KiB
80Runtime error453ms260828 KiB
81Runtime error389ms260820 KiB
82Runtime error370ms260804 KiB
83Runtime error354ms260800 KiB
84Runtime error342ms260792 KiB
85Runtime error333ms260796 KiB
86Accepted199ms79436 KiB
87Runtime error287ms260560 KiB
88Runtime error328ms260560 KiB
89Accepted358ms146284 KiB
90Accepted472ms162684 KiB
91Accepted714ms254692 KiB
92Runtime error497ms260552 KiB
93Runtime error381ms260544 KiB
94Runtime error382ms260536 KiB
95Runtime error381ms260524 KiB
96Runtime error388ms260496 KiB
97Runtime error361ms260496 KiB
98Runtime error342ms260504 KiB
99Runtime error407ms260504 KiB
100Runtime error381ms260276 KiB
101Runtime error345ms260280 KiB