108312024-04-16 10:25:51TomaSajtVállalati ügyeletcpp17Futási hiba 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] << ' ';
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1888 KiB
2Futási hiba391ms262860 KiB
subtask25/5
3Elfogadva3ms2312 KiB
4Elfogadva3ms2532 KiB
5Elfogadva3ms2896 KiB
6Elfogadva3ms3012 KiB
subtask38/8
7Elfogadva3ms2312 KiB
8Elfogadva3ms2532 KiB
9Elfogadva3ms2896 KiB
10Elfogadva3ms3012 KiB
11Elfogadva112ms60360 KiB
12Elfogadva120ms61356 KiB
13Elfogadva126ms62244 KiB
14Elfogadva197ms78456 KiB
subtask40/12
15Elfogadva3ms2312 KiB
16Elfogadva3ms2532 KiB
17Elfogadva3ms2896 KiB
18Elfogadva3ms3012 KiB
19Futási hiba284ms261420 KiB
20Futási hiba284ms261184 KiB
21Futási hiba286ms261156 KiB
22Futási hiba287ms261144 KiB
23Futási hiba328ms261112 KiB
24Futási hiba321ms261124 KiB
subtask517/17
25Elfogadva3ms2312 KiB
26Elfogadva3ms2532 KiB
27Elfogadva3ms2896 KiB
28Elfogadva3ms3012 KiB
29Elfogadva4ms4676 KiB
30Elfogadva308ms192552 KiB
31Elfogadva356ms192532 KiB
32Elfogadva46ms27300 KiB
33Elfogadva138ms75952 KiB
34Elfogadva4ms5016 KiB
35Elfogadva6ms5996 KiB
36Elfogadva29ms21356 KiB
37Elfogadva201ms113868 KiB
38Elfogadva12ms9328 KiB
39Elfogadva17ms13696 KiB
40Elfogadva13ms10328 KiB
41Elfogadva70ms41852 KiB
subtask60/28
42Futási hiba456ms260880 KiB
43Futási hiba391ms260848 KiB
44Futási hiba372ms260840 KiB
45Futási hiba358ms260836 KiB
46Futási hiba344ms260824 KiB
47Futási hiba333ms260808 KiB
48Elfogadva199ms79212 KiB
49Futási hiba289ms260788 KiB
50Futási hiba335ms260788 KiB
subtask70/30
51Elfogadva3ms4260 KiB
52Futási hiba388ms260788 KiB
53Elfogadva3ms2312 KiB
54Elfogadva3ms2532 KiB
55Elfogadva3ms2896 KiB
56Elfogadva3ms3012 KiB
57Elfogadva112ms60360 KiB
58Elfogadva120ms61356 KiB
59Elfogadva126ms62244 KiB
60Elfogadva197ms78456 KiB
61Futási hiba284ms261420 KiB
62Futási hiba284ms261184 KiB
63Futási hiba286ms261156 KiB
64Futási hiba287ms261144 KiB
65Futási hiba328ms261112 KiB
66Futási hiba321ms261124 KiB
67Elfogadva4ms4676 KiB
68Elfogadva308ms192552 KiB
69Elfogadva356ms192532 KiB
70Elfogadva46ms27300 KiB
71Elfogadva138ms75952 KiB
72Elfogadva4ms5016 KiB
73Elfogadva6ms5996 KiB
74Elfogadva29ms21356 KiB
75Elfogadva201ms113868 KiB
76Elfogadva12ms9328 KiB
77Elfogadva17ms13696 KiB
78Elfogadva13ms10328 KiB
79Elfogadva70ms41852 KiB
80Futási hiba456ms260880 KiB
81Futási hiba391ms260848 KiB
82Futási hiba372ms260840 KiB
83Futási hiba358ms260836 KiB
84Futási hiba344ms260824 KiB
85Futási hiba333ms260808 KiB
86Elfogadva199ms79212 KiB
87Futási hiba289ms260788 KiB
88Futási hiba335ms260788 KiB
89Elfogadva361ms146048 KiB
90Elfogadva393ms162528 KiB
91Elfogadva610ms254648 KiB
92Futási hiba493ms260800 KiB
93Futási hiba381ms260792 KiB
94Futási hiba382ms260780 KiB
95Futási hiba381ms260752 KiB
96Futási hiba389ms260768 KiB
97Futási hiba361ms260768 KiB
98Futási hiba344ms260772 KiB
99Futási hiba411ms260772 KiB
100Futási hiba361ms260776 KiB
101Futási hiba347ms260768 KiB