#pragma optimize "Ofast"
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<cmath>
#include<cassert>
using namespace std;
vector<int> edges[100005];
pair<int, int> times[100005];
int depth[100005];
int col[100005]; int cnt = 1;
vector<int> depthtimes[100005];
vector<int> nwcol[100005];
unordered_map<int, int> dwcol[100005];
unordered_map<int, pair<int, int>> stdepth;// unordered_map<int, int> cldepth;
int bestans = 0; int bestswap = 1e9;
long long sum = 0;
void dfs(int n, int d) {
times[n].first = cnt++;
depth[n] = d;
for (auto c : edges[n]) {
dfs(c, d+1);
}
times[n].second = cnt++;
}
void find(int n, int cl, bool found) {
// sum++;
if (found) {
stdepth[depth[n]].first++;
if (col[n] == cl) stdepth[depth[n]].second++;
}
for (auto c : edges[n]) {
if (col[n] == cl) find(c, cl, true);
else find(c, cl, found);
}
if (col[n] == cl && !found) { // highest node with cl
int curans = 0; int curswap = 0;
for (auto& p : stdepth) {
int t = dwcol[cl][p.first];
curans += min(p.second.first, t);
curswap += max(0, min(p.second.first, t)-p.second.second);
}
if (bestans == curans+1) {
bestswap = min(bestswap, curswap);
}
else if (bestans < curans+1) {
bestans = curans+1;
bestswap = curswap;
}
stdepth.clear();
}
}
int main() {
int n, k; cin>>n>>k;
for (int i = 0; i < n; i++) {
cin>>col[i];
}
for (int i = 1; i < n; i++) {
int x; cin>>x;
edges[x].push_back(i);
}
dfs(0, 0);
for (int i = 0; i < n; i++) {
dwcol[col[i]][depth[i]]++;
}
for (int i = 0; i < n; i++) {
depthtimes[depth[i]].push_back(times[i].first);
}
for (int i = 0; i <= n; i++) {
sort(depthtimes[i].begin(), depthtimes[i].end());
}
for (int i = 0; i < n; i++) {
nwcol[col[i]].push_back(i);
}
int sq = sqrt(n);
// overall, sum of all cnt^2 = n
for (int clr = 0; clr < k; clr++) {
if (nwcol[clr].size() >= sq) {
find(0, clr, false); // n algo, with log
}
else {
cout<<"big"<<endl;
continue;
for (auto i : nwcol[clr]) { // cnt^2 with
map<int, int> used;
map<int, int> swapped;
int curans = 0;
int curswap = 0;
for (auto j : nwcol[clr]) {
if (j == i || depth[j] <= depth[i]) continue;
int up = upper_bound(depthtimes[depth[j]].begin(), depthtimes[depth[j]].end(), times[i].second)-depthtimes[depth[j]].begin();
int low = lower_bound(depthtimes[depth[j]].begin(), depthtimes[depth[j]].end(), times[i].first)-depthtimes[depth[j]].begin();
if (up-low-used[depth[j]]>0) {
used[depth[j]]++;
curans++;
swapped[depth[j]]++;
curswap++;
}
if (times[i].first < times[j].first && times[j].second < times[i].second) {
if (swapped[depth[j]]>0) {
swapped[depth[j]]--;
curswap--;
}
}
}
if (bestans == curans+1) {
bestswap = min(bestswap, curswap);
}
else if (bestans < curans+1) {
bestans = curans+1;
bestswap = curswap;
}
}
}
}
// cout<<sum<<endl;
cout<<bestans<<" "<<bestswap<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |