108372024-04-16 12:31:03TomaSajtVállalati ügyeletcpp17Accepted 100/100439ms158440 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<int>> g;
vector<set<int>> sets;
vector<int> vals, mexes;

void dfs(int u) {
  sets[u].insert(vals[u]);
  for (int v : g[u]) {
    dfs(v);
    mexes[u] = max(mexes[u], mexes[v]);
    if (sets[u].size() < sets[v].size()) swap(sets[u], sets[v]);
    sets[u].insert(sets[v].begin(), sets[v].end());
  }
  auto it = sets[u].lower_bound(mexes[u]);
  while (it != 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);
  sets.resize(n + 1);
  mexes.resize(n + 1, 1);
  vals.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 >> vals[i];
  dfs(1);
  for (int i = 1; i <= n; i++) cout << mexes[i] << ' ';
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1888 KiB
2Accepted215ms101272 KiB
subtask25/5
3Accepted3ms2412 KiB
4Accepted3ms2624 KiB
5Accepted3ms2740 KiB
6Accepted3ms2812 KiB
subtask38/8
7Accepted3ms2412 KiB
8Accepted3ms2624 KiB
9Accepted3ms2740 KiB
10Accepted3ms2812 KiB
11Accepted130ms59876 KiB
12Accepted141ms61328 KiB
13Accepted149ms62196 KiB
14Accepted222ms78076 KiB
subtask412/12
15Accepted3ms2412 KiB
16Accepted3ms2624 KiB
17Accepted3ms2740 KiB
18Accepted3ms2812 KiB
19Accepted167ms107080 KiB
20Accepted167ms108316 KiB
21Accepted172ms109320 KiB
22Accepted245ms125296 KiB
23Accepted212ms125284 KiB
24Accepted188ms116036 KiB
subtask517/17
25Accepted3ms2412 KiB
26Accepted3ms2624 KiB
27Accepted3ms2740 KiB
28Accepted3ms2812 KiB
29Accepted4ms4608 KiB
30Accepted4ms5304 KiB
31Accepted4ms5292 KiB
32Accepted4ms5184 KiB
33Accepted4ms5500 KiB
34Accepted4ms5180 KiB
35Accepted4ms5576 KiB
36Accepted4ms5260 KiB
37Accepted4ms5640 KiB
38Accepted4ms5540 KiB
39Accepted4ms5200 KiB
40Accepted4ms5448 KiB
41Accepted4ms5644 KiB
subtask628/28
42Accepted298ms122920 KiB
43Accepted229ms110540 KiB
44Accepted230ms109740 KiB
45Accepted211ms114396 KiB
46Accepted206ms119572 KiB
47Accepted196ms124360 KiB
48Accepted223ms79564 KiB
49Accepted229ms126812 KiB
50Accepted196ms126788 KiB
subtask730/30
51Accepted3ms4832 KiB
52Accepted215ms103932 KiB
53Accepted3ms2412 KiB
54Accepted3ms2624 KiB
55Accepted3ms2740 KiB
56Accepted3ms2812 KiB
57Accepted130ms59876 KiB
58Accepted141ms61328 KiB
59Accepted149ms62196 KiB
60Accepted222ms78076 KiB
61Accepted167ms107080 KiB
62Accepted167ms108316 KiB
63Accepted172ms109320 KiB
64Accepted245ms125296 KiB
65Accepted212ms125284 KiB
66Accepted188ms116036 KiB
67Accepted4ms4608 KiB
68Accepted4ms5304 KiB
69Accepted4ms5292 KiB
70Accepted4ms5184 KiB
71Accepted4ms5500 KiB
72Accepted4ms5180 KiB
73Accepted4ms5576 KiB
74Accepted4ms5260 KiB
75Accepted4ms5640 KiB
76Accepted4ms5540 KiB
77Accepted4ms5200 KiB
78Accepted4ms5448 KiB
79Accepted4ms5644 KiB
80Accepted298ms122920 KiB
81Accepted229ms110540 KiB
82Accepted230ms109740 KiB
83Accepted211ms114396 KiB
84Accepted206ms119572 KiB
85Accepted196ms124360 KiB
86Accepted223ms79564 KiB
87Accepted229ms126812 KiB
88Accepted196ms126788 KiB
89Accepted270ms99284 KiB
90Accepted291ms106168 KiB
91Accepted409ms146404 KiB
92Accepted439ms158440 KiB
93Accepted214ms102976 KiB
94Accepted222ms113648 KiB
95Accepted229ms124280 KiB
96Accepted210ms100920 KiB
97Accepted199ms100308 KiB
98Accepted190ms100616 KiB
99Accepted233ms110052 KiB
100Accepted221ms103336 KiB
101Accepted195ms107392 KiB