Submission #1045468

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045468		ainta	Team Coding (EGOI24_teamcoding)	C++17	100 / 100	996 ms	62424 KiB

Main

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

#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
typedef long long ll;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned long long;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;

#define N_ 110000

vi E[N_], G[N_];
int n, K;
const int BL = 200;
int w[N_], Dep[N_], Num[N_], cnt, Ed[N_], Rev[N_];
int Left[N_], Right[N_], Ans, Ans2, T1[N_], T2[N_];
map<int,int>C[N_];
void DFS(int a){
    Num[a] = ++cnt;
    for(auto &x:E[a]){
        Dep[x]=Dep[a]+1;
        DFS(x);
    }
    Ed[a] = ++cnt;
}
void Do1(int a){
    int pv = -1, Mx = -1;
    for(auto &x:E[a]){
        Do1(x);
        if(Mx < si(C[x])){
            pv = x;
            Mx = si(C[x]);
        }
    }
    if(pv!=-1){
        swap(C[a],C[pv]);
    }
    C[a][Dep[a]]+=1;
    for(auto &x:E[a]){
        if(x==pv)continue;
        for(auto &[d,c] : C[x]) C[a][d] += c;
    }
    if(si(G[w[a]]) < BL){
        for(auto &t: G[w[a]]){
            T1[Dep[t]]++;
            if(Num[a] <= Num[t] && Num[t] <= Ed[a]){
                T2[Dep[t]]++;
            }
        }
        int s = 0, s2 = 0;
        for(auto &t: G[w[a]]){
            int d = Dep[t];
            if(!T1[d])continue;
            int c = C[a][d];
            s += min(T1[d], c);
            s2 += min(T2[d],c);
            T1[d]=T2[d]=0;
        }
        if(Ans < s || (Ans==s && Ans2 > s-s2)){
            Ans = s;
            Ans2 = s-s2;
        }
    }
}
int DMX, CC[N_], s2;
void Go(int a, int col){
    int d = Dep[a];
    CC[d]++;
    DMX = max(DMX, d);
    if(w[a]==col)s2++;

    for(auto &x: E[a]){
        Go(x,col);
    }
}
void Do2(int a, int col){
    if(w[a]==col){
        DMX = Dep[a];
        s2=0;
        Go(a, col);
        int s=0;
        rng(i,Dep[a],DMX){
            s += min(CC[i],T1[i]);
            CC[i]=0;
        }
        if(Ans < s || (Ans==s && Ans2 > s-s2)){
            Ans = s;
            Ans2 = s-s2;
        }
        return;
    }
    for(auto &x : E[a]){
        Do2(x, col);
    }
}

int main(){
    scanf("%d%d",&n,&K);
    rep(i,n){
        scanf("%d",&w[i]);
        G[w[i]].pb(i);
    }
    rng(i,1,n-1){
        int a;
        scanf("%d",&a);
        E[a].pb(i);
    }
    DFS(0);
    Do1(0);

    rep(i,K){
        if(si(G[i]) >= BL){
            for(auto &u: G[i])T1[Dep[u]]++;
            Do2(0,i);
            for(auto &u: G[i])T1[Dep[u]]--;
        }
    }
    printf("%d %d\n",Ans,Ans2);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:116:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |     scanf("%d%d",&n,&K);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:118:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         scanf("%d",&w[i]);
      |         ~~~~~^~~~~~~~~~~~
Main.cpp:123:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         scanf("%d",&a);
      |         ~~~~~^~~~~~~~~

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