Submission #1236358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236358		asdfghqwert	Team Coding (EGOI24_teamcoding)	C++20	100 / 100	1064 ms	29376 KiB

Main

#pragma GCC optimize("O3,unroll-loops,fast-math")
//#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
//#define int long long int

using namespace std;
const int T = 333;
const int INF = 1e9;

vector<vector<int>> g;
vector<int> c;
vector<int> fl;
vector<int> tin , tout;
vector<vector<int>> fltin , fltout;
vector<int> candi_cnt , flcount;
vector<vector<int>> candi_sz;

int target , timee , ansn = 0 , ansk = INF;

void pre_dfs(int u){
    tin[u] = timee;
    fltin[fl[u]].push_back(tin[u]);
    for(int v : g[u]){
        fl[v] = fl[u] + 1;
        timee++;
        pre_dfs(v);
    }
    tout[u] = timee;
    fltout[fl[u]].push_back(tout[u]);
}
void dfs(int u , int par){
    if(par == -1 && c[u] == target)par = u;
    if(par != -1){
        if(fl[u] - fl[par] == candi_sz[par].size())candi_sz[par].push_back(0);
        candi_sz[par][fl[u] - fl[par]]++;
    }
    if(c[u] == target){
        candi_cnt[par]++;
        flcount[fl[u]]++;
    }
    for(int v : g[u]){
        dfs(v , par);
    }
}
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n , k;cin >> n >> k;
    g.resize(n);c.resize(n);fl.resize(n);tin.resize(n);tout.resize(n);fltin.resize(n);fltout.resize(n);
    vector<vector<int>> c_v(k);
    for(int i = 0 ; i < n ;i++){
        cin >> c[i];
        c_v[c[i]].push_back(i);
    }
    for(int i = 1 ; i < n ; i++){
        int p;cin >> p;
        g[p].push_back(i);
    }
    pre_dfs(0);
    for(int idx = 0 ; idx < k ; idx++){
        if(c_v[idx].size() >= T){
            target = idx;
            candi_cnt.assign(n, 0);
            flcount.assign(n, 0);
            candi_sz.assign(n, vector<int>());
            dfs(0 , -1);
            for(int u = 0 ; u < n ; u++){
                if(candi_cnt[u] == 0)continue;
                int tans = 0;
                for(int f = 0 ; f < candi_sz[u].size() ; f++){
                    tans += min(candi_sz[u][f] , flcount[f + fl[u]]);
                }
                if(tans == ansn)ansk = min(ansk , ansn - candi_cnt[u]);
                if(tans > ansn){
                    ansn = tans;
                    ansk = ansn - candi_cnt[u];
                }
            }
        }        
        else{
            map<int, int> flc;
            for(int u : c_v[idx]){
                flc[fl[u]]++;
            }
            for(int u : c_v[idx]){
                int tans = 0;
                for(auto& [f, cnt] : flc){
                    int s = lower_bound(fltin[f].begin(), fltin[f].end(), tin[u]) - fltin[f].begin();
                    int e = upper_bound(fltout[f].begin(), fltout[f].end(), tout[u]) - fltout[f].begin();
                    tans += min(cnt, e - s);
                }
                if(tans >= ansn){
                    int szcnt = 0;
                    for(int v : c_v[idx]){
                        if(tin[v] >= tin[u] && tout[v] <= tout[u]) {
                            szcnt++;
                        }
                    }
                    if(tans == ansn) {
                        ansk = min(ansk, tans - szcnt);
                    }
                    if(tans > ansn) {
                        ansn = tans;
                        ansk = ansn - szcnt;
                    }
                }
            }
        }
       
    }
    cout << ansn << ' ' << ansk << '\n';

}

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