290322026-06-03 18:39:02algoproVállalati ügyeletcpp17Elfogadva 100/100437ms73524 KiB
// UUID: 4078208b-d4eb-4aca-8ab6-73f05583795b
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pll=pair<ll, ll>;

vector<ll> cnt, nagybaba, out;
vector<set<ll>> nap;
vector<vector<ll>> child;

void dfs_cnt(ll x){
	ll legnagyobb=-1;
	for (auto z:child[x]){
		dfs_cnt(z);
		cnt[x]+=cnt[z];
		if (cnt[z]>legnagyobb){
			legnagyobb=cnt[z];
			nagybaba[x]=z;
		}
	}
}

void dfs(ll x){
	for (auto z:child[x]){
		dfs(z);
	}
	for (auto z:child[x]){
		if (z!=nagybaba[x]){
			nap[nagybaba[x]].merge(nap[z]); //itt belepakolsz dolgokat a nagybabába mielőtt meghívod rá a dfs!
			//for (auto elem:nap[z]) nap[nagybaba[x]].insert(elem);
		}
		out[x]=max(out[x], out[z]);
	}
	if (nagybaba[x]!=-1){
		for (auto elem:nap[x]) nap[nagybaba[x]].insert(elem);
		swap(nap[x], nap[nagybaba[x]]);
	}
	while (nap[x].find(out[x])!=nap[x].end()) out[x]++;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	ll n; cin >> n;
	cnt.resize(n, 1);
	nagybaba.resize(n, -1);
	nap.resize(n);
	nap.resize(n);
	child.resize(n);
	out.resize(n, 1);
	for (ll i=0; i<n; i++){
		ll a; cin >> a; a--;
		if (i!=0) child[a].push_back(i);
	}
	for (ll i=0; i<n; i++){
		ll x; cin >> x;
		nap[i].insert(x);
	}
	dfs_cnt(0);
	dfs(0);
	for (auto z:out) cout << z << ' ';
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva209ms39732 KiB
subtask25/5
3Elfogadva1ms512 KiB
4Elfogadva1ms316 KiB
5Elfogadva1ms500 KiB
6Elfogadva1ms500 KiB
subtask38/8
7Elfogadva1ms512 KiB
8Elfogadva1ms316 KiB
9Elfogadva1ms500 KiB
10Elfogadva1ms500 KiB
11Elfogadva119ms30368 KiB
12Elfogadva120ms30580 KiB
13Elfogadva127ms30552 KiB
14Elfogadva207ms30448 KiB
subtask412/12
15Elfogadva1ms512 KiB
16Elfogadva1ms316 KiB
17Elfogadva1ms500 KiB
18Elfogadva1ms500 KiB
19Elfogadva174ms64344 KiB
20Elfogadva204ms64564 KiB
21Elfogadva210ms64820 KiB
22Elfogadva287ms72756 KiB
23Elfogadva250ms73524 KiB
24Elfogadva201ms68916 KiB
subtask517/17
25Elfogadva1ms512 KiB
26Elfogadva1ms316 KiB
27Elfogadva1ms500 KiB
28Elfogadva1ms500 KiB
29Elfogadva3ms564 KiB
30Elfogadva4ms1080 KiB
31Elfogadva4ms1080 KiB
32Elfogadva4ms820 KiB
33Elfogadva3ms820 KiB
34Elfogadva2ms564 KiB
35Elfogadva3ms564 KiB
36Elfogadva3ms820 KiB
37Elfogadva3ms828 KiB
38Elfogadva4ms792 KiB
39Elfogadva4ms1012 KiB
40Elfogadva3ms684 KiB
41Elfogadva3ms820 KiB
subtask628/28
42Elfogadva277ms37932 KiB
43Elfogadva246ms41012 KiB
44Elfogadva221ms47820 KiB
45Elfogadva228ms56464 KiB
46Elfogadva250ms64052 KiB
47Elfogadva229ms70360 KiB
48Elfogadva247ms30376 KiB
49Elfogadva331ms72756 KiB
50Elfogadva246ms73520 KiB
subtask730/30
51Elfogadva2ms316 KiB
52Elfogadva214ms39852 KiB
53Elfogadva1ms512 KiB
54Elfogadva1ms316 KiB
55Elfogadva1ms500 KiB
56Elfogadva1ms500 KiB
57Elfogadva119ms30368 KiB
58Elfogadva120ms30580 KiB
59Elfogadva127ms30552 KiB
60Elfogadva207ms30448 KiB
61Elfogadva174ms64344 KiB
62Elfogadva204ms64564 KiB
63Elfogadva210ms64820 KiB
64Elfogadva287ms72756 KiB
65Elfogadva250ms73524 KiB
66Elfogadva201ms68916 KiB
67Elfogadva3ms564 KiB
68Elfogadva4ms1080 KiB
69Elfogadva4ms1080 KiB
70Elfogadva4ms820 KiB
71Elfogadva3ms820 KiB
72Elfogadva2ms564 KiB
73Elfogadva3ms564 KiB
74Elfogadva3ms820 KiB
75Elfogadva3ms828 KiB
76Elfogadva4ms792 KiB
77Elfogadva4ms1012 KiB
78Elfogadva3ms684 KiB
79Elfogadva3ms820 KiB
80Elfogadva277ms37932 KiB
81Elfogadva246ms41012 KiB
82Elfogadva221ms47820 KiB
83Elfogadva228ms56464 KiB
84Elfogadva250ms64052 KiB
85Elfogadva229ms70360 KiB
86Elfogadva247ms30376 KiB
87Elfogadva331ms72756 KiB
88Elfogadva246ms73520 KiB
89Elfogadva328ms37000 KiB
90Elfogadva344ms37172 KiB
91Elfogadva414ms37248 KiB
92Elfogadva437ms37420 KiB
93Elfogadva284ms47412 KiB
94Elfogadva246ms55844 KiB
95Elfogadva323ms64340 KiB
96Elfogadva231ms40756 KiB
97Elfogadva202ms42172 KiB
98Elfogadva201ms45108 KiB
99Elfogadva247ms39732 KiB
100Elfogadva224ms44080 KiB
101Elfogadva211ms51852 KiB