Submission #1214824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214824		biank	Team Coding (EGOI24_teamcoding)	C++20	100 / 100	2249 ms	565164 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define forn(i,n) for(int i=0;i<int(n);i++)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<int,int> ii;

const int N=1e5+9;

int l[N];
vi adj[N];
unordered_map<int, int> cnt[N];
vi vals[N];

void dfs0(int u, int d=0){
    cnt[l[u]][d]++;
    vals[l[u]].pb(d);
    for(int v:adj[u]) dfs0(v,d+1);
}

map<int, int> count_by_color[N];
deque<int> count_by_depth[N];

const int LIMIT=150;

int res_by_color[N][LIMIT];

ii ans={0,0};
int n,k;

void dfs(int u, int d=0){
    count_by_color[u][l[u]]++;
    count_by_depth[u]={1};
    forn(c,LIMIT) res_by_color[u][c]=min(1,cnt[c][d]);
    for(int v:adj[u]){
        dfs(v,d+1);
        if(sz(count_by_color[v])>sz(count_by_color[u])) swap(count_by_color[u],count_by_color[v]);
        for(auto&[key,value]:count_by_color[v]) count_by_color[u][key]+=value; 
        count_by_depth[v].emplace_front(0);
        if(sz(count_by_depth[v])>sz(count_by_depth[u])) swap(count_by_depth[u],count_by_depth[v]);
        forn(c,LIMIT) res_by_color[u][c]+=res_by_color[v][c];
        forn(h,sz(count_by_depth[v])){
            forn(c,LIMIT){
                res_by_color[u][c]-=min(count_by_depth[u][h],cnt[c][h+d])+min(count_by_depth[v][h],cnt[c][h+d]);
            }
            count_by_depth[u][h]+=count_by_depth[v][h];
            forn(c,LIMIT){
                res_by_color[u][c]+=min(count_by_depth[u][h],cnt[c][h+d]);
            }
        }
    }
    int res=l[u]<=LIMIT?res_by_color[u][l[u]]:0;
    if(l[u]>LIMIT) for(int h:vals[l[u]]){
        if(h<d) continue;
        if(h-d>sz(count_by_depth[u])) break;
        res+=min(count_by_depth[u][h-d],cnt[l[u]][h]);
    }
    int cost=res-count_by_color[u][l[u]];
    ans=max(ans,ii{res,-cost});
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>n>>k;
    forn(i,n) cin>>l[i];
    bool flag=true;
    forsn(i,1,n){
        int b; cin>>b;
        adj[b].pb(i);
        if(b!=i-1) flag=false;
    }
    vi q(k,0);
    int res=0;
    dforn(i,n){
        res=max(res,++q[l[i]]);
    }
    if(flag){
        cout<<res<<' '<<0<<'\n';
        return 0;
    }
    vi colors(k);
    iota(all(colors),0);
    sort(all(colors),[&](const int &lhs, const int &rhs){
        return q[lhs]>q[rhs];
    });
    vi pos_by_color(k);
    forn(i,k) pos_by_color[colors[i]]=i;
    forn(i,n) l[i]=pos_by_color[l[i]];
    dfs0(0);
    forn(i,k){
        sort(all(vals[i]));
        vals[i].erase(unique(all(vals[i])),end(vals[i]));
    }
    dfs(0);
    cout<<ans.fst<<' '<<-ans.snd<<'\n';
    
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 19 / 19
• Subtask 3: 27 / 27
• Subtask 4: 23 / 23
• Subtask 5: 19 / 19