108322024-04-16 10:27:05TomaSajtVállalati ügyeletcpp17Futási hiba 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] << ' ';
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1760 KiB
2Futási hiba372ms263016 KiB
subtask25/5
3Elfogadva3ms2160 KiB
4Elfogadva3ms2384 KiB
5Elfogadva3ms2464 KiB
6Elfogadva3ms2696 KiB
subtask38/8
7Elfogadva3ms2160 KiB
8Elfogadva3ms2384 KiB
9Elfogadva3ms2464 KiB
10Elfogadva3ms2696 KiB
11Elfogadva118ms59964 KiB
12Elfogadva120ms60928 KiB
13Elfogadva126ms62152 KiB
14Elfogadva186ms78292 KiB
subtask40/12
15Elfogadva3ms2160 KiB
16Elfogadva3ms2384 KiB
17Elfogadva3ms2464 KiB
18Elfogadva3ms2696 KiB
19Futási hiba284ms261536 KiB
20Futási hiba286ms261424 KiB
21Futási hiba287ms261416 KiB
22Futási hiba289ms261400 KiB
23Futási hiba330ms261388 KiB
24Futási hiba321ms261160 KiB
subtask517/17
25Elfogadva3ms2160 KiB
26Elfogadva3ms2384 KiB
27Elfogadva3ms2464 KiB
28Elfogadva3ms2696 KiB
29Elfogadva4ms4644 KiB
30Elfogadva314ms192440 KiB
31Elfogadva356ms192444 KiB
32Elfogadva46ms27508 KiB
33Elfogadva137ms75868 KiB
34Elfogadva4ms4848 KiB
35Elfogadva6ms5828 KiB
36Elfogadva32ms21520 KiB
37Elfogadva182ms113848 KiB
38Elfogadva10ms9424 KiB
39Elfogadva17ms13708 KiB
40Elfogadva13ms10340 KiB
41Elfogadva70ms41964 KiB
subtask60/28
42Futási hiba453ms260828 KiB
43Futási hiba389ms260820 KiB
44Futási hiba370ms260804 KiB
45Futási hiba354ms260800 KiB
46Futási hiba342ms260792 KiB
47Futási hiba333ms260796 KiB
48Elfogadva199ms79436 KiB
49Futási hiba287ms260560 KiB
50Futási hiba328ms260560 KiB
subtask70/30
51Elfogadva3ms4480 KiB
52Futási hiba360ms260536 KiB
53Elfogadva3ms2160 KiB
54Elfogadva3ms2384 KiB
55Elfogadva3ms2464 KiB
56Elfogadva3ms2696 KiB
57Elfogadva118ms59964 KiB
58Elfogadva120ms60928 KiB
59Elfogadva126ms62152 KiB
60Elfogadva186ms78292 KiB
61Futási hiba284ms261536 KiB
62Futási hiba286ms261424 KiB
63Futási hiba287ms261416 KiB
64Futási hiba289ms261400 KiB
65Futási hiba330ms261388 KiB
66Futási hiba321ms261160 KiB
67Elfogadva4ms4644 KiB
68Elfogadva314ms192440 KiB
69Elfogadva356ms192444 KiB
70Elfogadva46ms27508 KiB
71Elfogadva137ms75868 KiB
72Elfogadva4ms4848 KiB
73Elfogadva6ms5828 KiB
74Elfogadva32ms21520 KiB
75Elfogadva182ms113848 KiB
76Elfogadva10ms9424 KiB
77Elfogadva17ms13708 KiB
78Elfogadva13ms10340 KiB
79Elfogadva70ms41964 KiB
80Futási hiba453ms260828 KiB
81Futási hiba389ms260820 KiB
82Futási hiba370ms260804 KiB
83Futási hiba354ms260800 KiB
84Futási hiba342ms260792 KiB
85Futási hiba333ms260796 KiB
86Elfogadva199ms79436 KiB
87Futási hiba287ms260560 KiB
88Futási hiba328ms260560 KiB
89Elfogadva358ms146284 KiB
90Elfogadva472ms162684 KiB
91Elfogadva714ms254692 KiB
92Futási hiba497ms260552 KiB
93Futási hiba381ms260544 KiB
94Futási hiba382ms260536 KiB
95Futási hiba381ms260524 KiB
96Futási hiba388ms260496 KiB
97Futási hiba361ms260496 KiB
98Futási hiba342ms260504 KiB
99Futási hiba407ms260504 KiB
100Futási hiba381ms260276 KiB
101Futási hiba345ms260280 KiB