108352024-04-16 12:29:29TomaSajtVállalati ügyeletcpp17Accepted 100/100439ms158540 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) {
  subtree_sets[u].insert(val[u]);
  for (int v : g[u]) {
    dfs(v);
    mexes[u] = max(mexes[u], mexes[v]);
    if (subtree_sets[u].size() < subtree_sets[v].size()) swap(subtree_sets[u], subtree_sets[v]);
    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
1Accepted3ms1892 KiB
2Accepted214ms101308 KiB
subtask25/5
3Accepted3ms2196 KiB
4Accepted3ms2268 KiB
5Accepted3ms2500 KiB
6Accepted3ms2708 KiB
subtask38/8
7Accepted3ms2196 KiB
8Accepted3ms2268 KiB
9Accepted3ms2500 KiB
10Accepted3ms2708 KiB
11Accepted122ms59748 KiB
12Accepted143ms60980 KiB
13Accepted149ms62176 KiB
14Accepted259ms78100 KiB
subtask412/12
15Accepted3ms2196 KiB
16Accepted3ms2268 KiB
17Accepted3ms2500 KiB
18Accepted3ms2708 KiB
19Accepted157ms107280 KiB
20Accepted167ms108276 KiB
21Accepted172ms109704 KiB
22Accepted229ms125800 KiB
23Accepted201ms125880 KiB
24Accepted178ms116492 KiB
subtask517/17
25Accepted3ms2196 KiB
26Accepted3ms2268 KiB
27Accepted3ms2500 KiB
28Accepted3ms2708 KiB
29Accepted4ms4744 KiB
30Accepted4ms5096 KiB
31Accepted4ms5356 KiB
32Accepted4ms5364 KiB
33Accepted4ms5488 KiB
34Accepted4ms5252 KiB
35Accepted4ms5748 KiB
36Accepted4ms5636 KiB
37Accepted4ms5748 KiB
38Accepted4ms5276 KiB
39Accepted4ms5496 KiB
40Accepted4ms5652 KiB
41Accepted4ms5712 KiB
subtask628/28
42Accepted298ms123176 KiB
43Accepted250ms111028 KiB
44Accepted215ms110104 KiB
45Accepted225ms114736 KiB
46Accepted221ms120164 KiB
47Accepted196ms124948 KiB
48Accepted219ms80300 KiB
49Accepted229ms127088 KiB
50Accepted200ms127100 KiB
subtask730/30
51Accepted3ms5252 KiB
52Accepted215ms104420 KiB
53Accepted3ms2196 KiB
54Accepted3ms2268 KiB
55Accepted3ms2500 KiB
56Accepted3ms2708 KiB
57Accepted122ms59748 KiB
58Accepted143ms60980 KiB
59Accepted149ms62176 KiB
60Accepted259ms78100 KiB
61Accepted157ms107280 KiB
62Accepted167ms108276 KiB
63Accepted172ms109704 KiB
64Accepted229ms125800 KiB
65Accepted201ms125880 KiB
66Accepted178ms116492 KiB
67Accepted4ms4744 KiB
68Accepted4ms5096 KiB
69Accepted4ms5356 KiB
70Accepted4ms5364 KiB
71Accepted4ms5488 KiB
72Accepted4ms5252 KiB
73Accepted4ms5748 KiB
74Accepted4ms5636 KiB
75Accepted4ms5748 KiB
76Accepted4ms5276 KiB
77Accepted4ms5496 KiB
78Accepted4ms5652 KiB
79Accepted4ms5712 KiB
80Accepted298ms123176 KiB
81Accepted250ms111028 KiB
82Accepted215ms110104 KiB
83Accepted225ms114736 KiB
84Accepted221ms120164 KiB
85Accepted196ms124948 KiB
86Accepted219ms80300 KiB
87Accepted229ms127088 KiB
88Accepted200ms127100 KiB
89Accepted275ms99528 KiB
90Accepted287ms106356 KiB
91Accepted412ms146600 KiB
92Accepted439ms158540 KiB
93Accepted216ms103180 KiB
94Accepted222ms113836 KiB
95Accepted250ms124508 KiB
96Accepted212ms101092 KiB
97Accepted214ms100452 KiB
98Accepted207ms100632 KiB
99Accepted234ms110208 KiB
100Accepted221ms103184 KiB
101Accepted209ms107364 KiB