108312024-04-16 10:25:51TomaSajtVállalati ügyeletcpp17Runtime error 30/100610ms262860 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 == 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
1Accepted3ms1888 KiB
2Runtime error391ms262860 KiB
subtask25/5
3Accepted3ms2312 KiB
4Accepted3ms2532 KiB
5Accepted3ms2896 KiB
6Accepted3ms3012 KiB
subtask38/8
7Accepted3ms2312 KiB
8Accepted3ms2532 KiB
9Accepted3ms2896 KiB
10Accepted3ms3012 KiB
11Accepted112ms60360 KiB
12Accepted120ms61356 KiB
13Accepted126ms62244 KiB
14Accepted197ms78456 KiB
subtask40/12
15Accepted3ms2312 KiB
16Accepted3ms2532 KiB
17Accepted3ms2896 KiB
18Accepted3ms3012 KiB
19Runtime error284ms261420 KiB
20Runtime error284ms261184 KiB
21Runtime error286ms261156 KiB
22Runtime error287ms261144 KiB
23Runtime error328ms261112 KiB
24Runtime error321ms261124 KiB
subtask517/17
25Accepted3ms2312 KiB
26Accepted3ms2532 KiB
27Accepted3ms2896 KiB
28Accepted3ms3012 KiB
29Accepted4ms4676 KiB
30Accepted308ms192552 KiB
31Accepted356ms192532 KiB
32Accepted46ms27300 KiB
33Accepted138ms75952 KiB
34Accepted4ms5016 KiB
35Accepted6ms5996 KiB
36Accepted29ms21356 KiB
37Accepted201ms113868 KiB
38Accepted12ms9328 KiB
39Accepted17ms13696 KiB
40Accepted13ms10328 KiB
41Accepted70ms41852 KiB
subtask60/28
42Runtime error456ms260880 KiB
43Runtime error391ms260848 KiB
44Runtime error372ms260840 KiB
45Runtime error358ms260836 KiB
46Runtime error344ms260824 KiB
47Runtime error333ms260808 KiB
48Accepted199ms79212 KiB
49Runtime error289ms260788 KiB
50Runtime error335ms260788 KiB
subtask70/30
51Accepted3ms4260 KiB
52Runtime error388ms260788 KiB
53Accepted3ms2312 KiB
54Accepted3ms2532 KiB
55Accepted3ms2896 KiB
56Accepted3ms3012 KiB
57Accepted112ms60360 KiB
58Accepted120ms61356 KiB
59Accepted126ms62244 KiB
60Accepted197ms78456 KiB
61Runtime error284ms261420 KiB
62Runtime error284ms261184 KiB
63Runtime error286ms261156 KiB
64Runtime error287ms261144 KiB
65Runtime error328ms261112 KiB
66Runtime error321ms261124 KiB
67Accepted4ms4676 KiB
68Accepted308ms192552 KiB
69Accepted356ms192532 KiB
70Accepted46ms27300 KiB
71Accepted138ms75952 KiB
72Accepted4ms5016 KiB
73Accepted6ms5996 KiB
74Accepted29ms21356 KiB
75Accepted201ms113868 KiB
76Accepted12ms9328 KiB
77Accepted17ms13696 KiB
78Accepted13ms10328 KiB
79Accepted70ms41852 KiB
80Runtime error456ms260880 KiB
81Runtime error391ms260848 KiB
82Runtime error372ms260840 KiB
83Runtime error358ms260836 KiB
84Runtime error344ms260824 KiB
85Runtime error333ms260808 KiB
86Accepted199ms79212 KiB
87Runtime error289ms260788 KiB
88Runtime error335ms260788 KiB
89Accepted361ms146048 KiB
90Accepted393ms162528 KiB
91Accepted610ms254648 KiB
92Runtime error493ms260800 KiB
93Runtime error381ms260792 KiB
94Runtime error382ms260780 KiB
95Runtime error381ms260752 KiB
96Runtime error389ms260768 KiB
97Runtime error361ms260768 KiB
98Runtime error344ms260772 KiB
99Runtime error411ms260772 KiB
100Runtime error361ms260776 KiB
101Runtime error347ms260768 KiB