294312026-06-10 15:36:47LazurAndrasVállalati ügyeletcpp17Elfogadva 100/100209ms27452 KiB
#include <bits/stdc++.h>
using namespace std;
const int N = 200002;

int n;
vector<vector<int>>g(N);
vector<int>a(N), ans(N), s(N);
vector<bool>vis(N);
int mex = 1;

void add(int v)
{
    vis[a[v]] = 1;
    for(int u : g[v]) add(u);
}

void rem(int v)
{
    vis[a[v]] = 0;
    for(int u : g[v]) rem(u);
}

void dfs(int v)
{
    int heavy = -1;
    for(int u : g[v]) if(heavy == -1 || s[u] > s[heavy]) heavy = u;
    for(int u : g[v])
    {
        if(u == heavy) continue;
        dfs(u);
        rem(u);
        mex = 1;
    }
    if(heavy != -1) dfs(heavy);
    vis[a[v]] = 1;
    for(int u : g[v]) if(u != heavy) add(u);
    while(vis[mex]) mex++;
    ans[v] = mex;
}

signed main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);
	cin >> n;
    for(int i = 0; i < n; i++)
    {
        int p; cin >> p; p--;
        if(i != 0) g[p].push_back(i);
    }
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = n-1; i >= 0; i--)
    {
        s[i] = 1;
        for(int u : g[i]) s[i] += s[u];
    }
    dfs(0);
    for(int i = 0; i < n; i++) cout << ans[i] << " ";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva8ms7660 KiB
2Elfogadva98ms12084 KiB
subtask25/5
3Elfogadva8ms7480 KiB
4Elfogadva7ms7492 KiB
5Elfogadva8ms7476 KiB
6Elfogadva7ms7476 KiB
subtask38/8
7Elfogadva8ms7480 KiB
8Elfogadva7ms7492 KiB
9Elfogadva8ms7476 KiB
10Elfogadva7ms7476 KiB
11Elfogadva59ms8624 KiB
12Elfogadva64ms8788 KiB
13Elfogadva64ms8684 KiB
14Elfogadva64ms8752 KiB
subtask412/12
15Elfogadva8ms7480 KiB
16Elfogadva7ms7492 KiB
17Elfogadva8ms7476 KiB
18Elfogadva7ms7476 KiB
19Elfogadva103ms27084 KiB
20Elfogadva97ms26932 KiB
21Elfogadva97ms26876 KiB
22Elfogadva104ms26680 KiB
23Elfogadva101ms27452 KiB
24Elfogadva104ms27356 KiB
subtask517/17
25Elfogadva8ms7480 KiB
26Elfogadva7ms7492 KiB
27Elfogadva8ms7476 KiB
28Elfogadva7ms7476 KiB
29Elfogadva7ms7476 KiB
30Elfogadva9ms7476 KiB
31Elfogadva9ms7476 KiB
32Elfogadva8ms7668 KiB
33Elfogadva9ms7476 KiB
34Elfogadva8ms7476 KiB
35Elfogadva7ms7476 KiB
36Elfogadva8ms7560 KiB
37Elfogadva7ms7476 KiB
38Elfogadva7ms7476 KiB
39Elfogadva8ms7476 KiB
40Elfogadva7ms7548 KiB
41Elfogadva8ms7520 KiB
subtask628/28
42Elfogadva109ms11184 KiB
43Elfogadva98ms12656 KiB
44Elfogadva101ms15924 KiB
45Elfogadva98ms19592 KiB
46Elfogadva105ms23088 KiB
47Elfogadva101ms25984 KiB
48Elfogadva67ms8620 KiB
49Elfogadva97ms26592 KiB
50Elfogadva100ms27344 KiB
subtask730/30
51Elfogadva7ms7476 KiB
52Elfogadva101ms12080 KiB
53Elfogadva8ms7480 KiB
54Elfogadva7ms7492 KiB
55Elfogadva8ms7476 KiB
56Elfogadva7ms7476 KiB
57Elfogadva59ms8624 KiB
58Elfogadva64ms8788 KiB
59Elfogadva64ms8684 KiB
60Elfogadva64ms8752 KiB
61Elfogadva103ms27084 KiB
62Elfogadva97ms26932 KiB
63Elfogadva97ms26876 KiB
64Elfogadva104ms26680 KiB
65Elfogadva101ms27452 KiB
66Elfogadva104ms27356 KiB
67Elfogadva7ms7476 KiB
68Elfogadva9ms7476 KiB
69Elfogadva9ms7476 KiB
70Elfogadva8ms7668 KiB
71Elfogadva9ms7476 KiB
72Elfogadva8ms7476 KiB
73Elfogadva7ms7476 KiB
74Elfogadva8ms7560 KiB
75Elfogadva7ms7476 KiB
76Elfogadva7ms7476 KiB
77Elfogadva8ms7476 KiB
78Elfogadva7ms7548 KiB
79Elfogadva8ms7520 KiB
80Elfogadva109ms11184 KiB
81Elfogadva98ms12656 KiB
82Elfogadva101ms15924 KiB
83Elfogadva98ms19592 KiB
84Elfogadva105ms23088 KiB
85Elfogadva101ms25984 KiB
86Elfogadva67ms8620 KiB
87Elfogadva97ms26592 KiB
88Elfogadva100ms27344 KiB
89Elfogadva182ms11052 KiB
90Elfogadva177ms11060 KiB
91Elfogadva177ms11064 KiB
92Elfogadva209ms11024 KiB
93Elfogadva112ms15412 KiB
94Elfogadva107ms19256 KiB
95Elfogadva104ms22964 KiB
96Elfogadva100ms12596 KiB
97Elfogadva97ms13124 KiB
98Elfogadva100ms14644 KiB
99Elfogadva104ms12112 KiB
100Elfogadva97ms14132 KiB
101Elfogadva101ms17528 KiB