Submission #1065335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065335		Dan4Life	Team Coding (EGOI24_teamcoding)	C++17	50 / 100	4075 ms	53536 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ar2 = array<int,2>;
const int mxN = (int)1e5+10;
const int INF = (int)1e9;
int n, k;
vector<int> adj[mxN];
ar2 ans{0,-INF};
vector<int> col[mxN];
int a[mxN], dep[mxN], sub[mxN];
vector<int> S[mxN];
set<ar2> Dep[mxN];
int dfs_timer, st[mxN], en[mxN];

void dfs1(int s, int p){
    sub[s] = 1; st[s]=++dfs_timer;
    if(p!=-1) dep[s]=dep[p]+1;
    for(auto u : adj[s]){
        if(u==p) continue;
        dfs1(u,s); sub[s]+=sub[u];
    }
    en[s] = dfs_timer;
}

bool upper(int a, int b){
    return st[a]<=st[b] and en[a]>=en[b];
}

void dfs(int s, int p){
    S[s].pb(s); Dep[s].insert({dep[s],1});
    for(auto u : adj[s]){
        if(u==p) continue;
        dfs(u,s);
        if(sz(S[s]) < sz(S[u])) S[s].swap(S[u]), Dep[s].swap(Dep[u]);
        for(auto v : S[u]) S[s].pb(v);
        for(auto [v,w] : Dep[u]){
            auto itr = Dep[s].lower_bound({v,-1});
            if(itr!=end(Dep[s]) and (*itr)[0]==v){
                int cur = (*itr)[1];
                Dep[s].erase(itr);
                Dep[s].insert({v,cur+w});
            }
            else Dep[s].insert({v,w});
        }
    }
    if(min(sub[s],sz(col[a[s]])) < ans[0]) return;
    
    auto cur = ar2({0,0});
    unordered_map<int,int> tot; tot.clear();
    for(auto u : col[a[s]]){
        if(upper(s,u)) cur[0]++,tot[dep[u]]++;
    }
    for(auto u : col[a[s]]){
        if(upper(s,u)) continue;
        auto itr = Dep[s].lower_bound({dep[u],-1});
        if(itr!=end(Dep[s]) and (*itr)[0]==dep[u]){
            if(tot[dep[u]] < (*itr)[1]){
                cur[0]++, cur[1]--; tot[dep[u]]++;
            }
        }
    }
    ans = max(ans, cur);
}

int main(){
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> a[i]; col[a[i]].pb(i);
    }
    for(int i = 1; i < n; i++){
        int x; cin >> x; adj[i].pb(x), adj[x].pb(i);
    }
    dfs1(0,-1); 
    for(int i = 0; i < n; i++) 
        sort(all(adj[i]),[&](int a, int b){return sub[a]>sub[b]; });
    dfs(0,-1); cout << ans[0] << " " << -ans[1] << "\n";
}

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