Submission #1124792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124792		salmon	Team Coding (EGOI24_teamcoding)	C++20	42 / 100	4094 ms	47988 KiB

Main

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

int N;
int K;
int lst[100100];
int parent[100100];
vector<int> children[100100];
int num[100100];
vector<int> srt;
vector<int> lc[100100];
const int B = 500;
int pre[100100];
int post[100100];
int d[100100];
int cont = 0;
int templst[100100];
bool lo[100100];
pair<int,int> ans;

void dfs(int i, int de){
    d[i] = de;
    pre[i] = cont;

    cont++;

    for(int j : children[i]){
        dfs(j,de + 1);
    }

    post[i] = cont - 1;
}

vector<int>* solve(int i){
    vector<vector<int>*> v;
    pair<int,int> p = {0,-1};
    vector<int>* vec = new vector<int>();

    for(int j : children[i]){
        v.push_back(solve(j));
        p = max(p,make_pair( (int) (v.back() -> size()), (int)v.size() - 1 ));
    }

    if(v.empty()){
        vec -> push_back(1);
    }
    else{
        vec = v[p.second];

        for(int j = 0; j < v.size(); j++){
            if(j == p.second) continue;

            int it = vec -> size() - 1;

            while(! (v[j] -> empty()) ){
                (*vec)[it] += v[j] -> back();
                v[j] -> pop_back();
                it--;
            }
        }

        vec -> push_back(1);
    }

    if(lo[lst[i]]){
        int k = lst[i];
        int ans = 0;
        int ans1 = 0;

        for(int j : lc[k]){
            if(pre[i] <= pre[j] && pre[j] <= post[i]) ans1++;
            templst[d[j]]++;
        }

        //printf("s: ");
        for(int a = d[i], it = vec -> size() - 1; it >= 0; a++,it--){
            ans += min( (*vec)[it], templst[a]);
            //printf("%d ",templst[a]);
        }
        //printf("\n");

        ans1 = ans - ans1;
        //printf("%d %d\n",ans,ans1);

        ::ans = max(::ans,{ans,-ans1});

        for(int j : lc[k]){
            templst[d[j]]--;
        }
    }

    return vec;
}

pair<vector<int>*,vector<int>*> solve1(int i, int k){
    vector<vector<int>*> v;
    vector<vector<int>*> v1;
    pair<int,int> p = {0,-1};
    vector<int>* vec = new vector<int>();
    vector<int>* vec1 = new vector<int>();

    for(int j : children[i]){
        pair<vector<int>*,vector<int>*> ii = solve1(j,k);
        v.push_back(ii.first);
        v1.push_back(ii.second);
        p = max(p,make_pair( (int) (v.back() -> size()), (int)v.size() - 1 ));
    }

    if(v.empty()){
        vec -> push_back(1);
        if(lst[i] == k) vec1 -> push_back(1);
        else vec1 -> push_back(0);
    }
    else{
        vec = v[p.second];

        for(int j = 0; j < v.size(); j++){
            if(j == p.second) continue;

            int it = vec -> size() - 1;

            while(! (v[j] -> empty()) ){
                (*vec)[it] += v[j] -> back();
                v[j] -> pop_back();
                it--;
            }
        }

        vec -> push_back(1);

        vec1 = v1[p.second];

        for(int j = 0; j < v.size(); j++){
            if(j == p.second) continue;

            int it = vec1 -> size() - 1;

            while(! (v1[j] -> empty()) ){
                (*vec1)[it] += v1[j] -> back();
                v1[j] -> pop_back();
                it--;
            }
        }

        if(lst[i] == k) vec1 -> push_back(1);
        else vec1 -> push_back(0);
    }

    if(lst[i] == k){
        int ans = 0;
        int ans1 = 0;

        for(int a = d[i], it = vec -> size() - 1; it >= 0; a++,it--){
            ans += min( (*vec)[it], templst[a]);
            ans1 += (*vec1)[it];
        }

        ans1 = ans - ans1;

        ::ans = max(::ans,{ans,-ans1});
    }

    return {vec,vec1};
}

int main(){
    scanf(" %d",&N);
    scanf(" %d",&K);

    for(int i = 0; i < K; i++){
        num[i] = 0;
        lo[i] = false;
        templst[i] = 0;
    }

    for(int i = 0; i < N; i++){
        scanf(" %d",&lst[i]);
        num[lst[i]]++;
        lc[lst[i]].push_back(i);
    }

    parent[0] = -1;
    for(int i = 1; i < N; i++){
        scanf(" %d",&parent[i]);
        children[parent[i]].push_back(i);
    }

    dfs(0,0);

    for(int i = 0; i < K; i++){
        if(num[i] >= B){
            srt.push_back(i);
        }
        else lo[i] = true;
    }

    ans = {0,-1};

    solve(0);

    //printf("%d %d",ans.first,-ans.second);

    for(int i : srt){
        for(int i = 0; i < N; i++){
            templst[i] = 0;
        }
        for(int j : lc[i]){
            templst[d[j]]++;
        }
        solve1(0,i);
    }

    printf("%d %d",ans.first,-ans.second);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:167:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
Main.cpp:168:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |     scanf(" %d",&K);
      |     ~~~~~^~~~~~~~~~
Main.cpp:177:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |         scanf(" %d",&lst[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
Main.cpp:184:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |         scanf(" %d",&parent[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~

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