Submission #1130067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130067		irmuun	Team Coding (EGOI24_teamcoding)	C++20	50 / 100	4096 ms	23748 KiB

Main

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const int N=1e5;

int n,k;
int l[N],b[N],dep[N],tin[N],tout[N],cur=0;
vector<int>g[N],L[N];
vector<int>ver[N];

void dfs(int x){
    tin[x]=cur++;
    ver[dep[x]].pb(tin[x]);
    for(int y:g[x]){
        dep[y]=dep[x]+1;
        dfs(y);
    }
    tout[x]=cur++;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>l[i];
        L[l[i]].pb(i);
    }
    for(int i=1;i<n;i++){
        cin>>b[i];
        g[b[i]].pb(i);
    }
    dep[0]=0;
    dfs(0);
    vector<int>count(n,0),used(n,0);
    int ans=0,op=0;
    for(int i=0;i<k;i++){
        if(L[i].empty()) continue;
        for(int x:L[i]){
            int res=1,mn=0;
            set<int>st;
            for(int y:L[i]){
                if(dep[y]<=dep[x]) continue;
                st.insert(dep[y]);
                count[dep[y]]++;
                if(tin[x]<tin[y]&&tout[y]<tout[x]){
                    used[dep[y]]++;
                }
            }
            for(int d:st){
                int slot=upper_bound(all(ver[d]),tout[x])-lower_bound(all(ver[d]),tin[x]);
                res+=min(slot,count[d]);
                mn+=min(slot,count[d])-used[d];
            }
            if(res>ans){
                ans=res;
                op=mn;
            }
            else if(res==ans){
                op=min(op,mn);
            }
            for(int y:L[i]){
                if(dep[y]<=dep[x]) continue;
                count[dep[y]]--;
                if(tin[x]<tin[y]&&tout[y]<tout[x]){
                    used[dep[y]]--;
                }
            }
        }
    }
    cout<<ans<<' '<<op;
}

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