Submission #1148514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148514		Ghulam_Junaid	Team Coding (EGOI24_teamcoding)	C++20	100 / 100	1081 ms	142744 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 100;
int n, k, par[N], a[N], h[N], ans[N], sub_ans[N];
map<int, int> cnt[N], anc, sac[N];
vector<int> g[N];
deque<int> dq[N];
bool good[N];

void dfs(int v){
    cnt[a[v]][h[v]]++;

    if (anc.find(a[v]) == anc.end()) good[v] = 1;
    anc[a[v]]++;

    for (int u : g[v]){
        h[u] = h[v] + 1;
        dfs(u);
    }
    anc[a[v]]--;
    if (anc[a[v]] == 0) anc.erase(a[v]);
}

void calc(int v){
    int mx = -1;
    for (int u : g[v]){
        calc(u);
        if (mx == -1 or dq[u].size() > dq[mx].size())
            mx = u;
    }

    if (mx == -1){
        dq[v].push_front(1);
        sac[v][a[v]]++;
        if (good[v]) ans[v] = 1, sub_ans[v] = 1;
        return ;
    }

    swap(dq[v], dq[mx]);
    swap(sac[v], sac[mx]);
    for (int u : g[v]){
        if (u == mx) continue;
        for (int i = 0; i < dq[u].size(); i ++)
            dq[v][i] += dq[u][i];
        for (auto [val, c] : sac[u])
            sac[v][val] += c;
    }
    dq[v].push_front(1);
    sac[v][a[v]]++;

    if (!good[v]) return ;
    for (auto [lvl, c] : cnt[a[v]]){
        int l = lvl - h[v];
        if (0 <= l and l < dq[v].size())
            ans[v] += min(c, dq[v][l]);
    }
    sub_ans[v] = sac[v][a[v]];
}

int main(){
    cin >> n >> k;
    for (int i = 0; i < n; i ++)
        cin >> a[i];
    for (int i = 1; i < n; i ++)
        cin >> par[i], g[par[i]].push_back(i);
    
    dfs(0);
    calc(0);

    int mx = 0, mn = n;
    for (int v = 0; v < n; v ++){
        if (!good[v]) continue;
        if (mx < ans[v] or (mx == ans[v] and mn > (ans[v] - sub_ans[v])))
            mx = ans[v], mn = ans[v] - sub_ans[v];
    }
    cout << mx << " " << mn << endl;
}

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