제출 #1195022

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195022		veehj	Team Coding (EGOI24_teamcoding)	C++20	23 / 100	4089 ms	1114112 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define pb push_back
#define sz(a) (ll) a.size()
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for(int i=a; i<b; i++)
#define rrep(i, a, b) for(ll i=a; i>=b; i--)
#define vl vector<ll>
#define vpll vector<pair<ll, ll>>
#define vvl vector<vector<ll>>
#define pll pair<ll, ll>
int n, k, mxlvl, timer;
pair<int, int> ans;
vector<int> lvl, pa, colour, pl, sz, pltoid;
vector<vector<int>> flr, cld;

void assign_lvl(int id){
  mxlvl=max(mxlvl, lvl[id]);
  pl[id]=timer;
  pltoid[timer]=id;
  timer++;
  sz[id]=1;
  for(auto& u : cld[id]){
    lvl[u]=lvl[id]+1;
    assign_lvl(u);
    sz[id]+=sz[u];
  }
}

void find(int id){
  int currpl=pl[id];
  vector<int> canfill(mxlvl, 0), have(mxlvl, 0);
  for(int i=0; i<sz[id]; i++){
    int currid=pltoid[currpl];
    canfill[lvl[currid]]++;
    if(colour[currid]==colour[id]) have[lvl[currid]]++;
    currpl++;
  }
  pair<int, int> currans={0, 0};
  for(int i=0; i<mxlvl; i++){
    if(canfill[i]==0) continue;
    currans.fi+=min(canfill[i], flr[i][colour[id]]);
    if(canfill[i]>have[i] && flr[i][colour[id]]>have[i]){
      currans.se+=min(canfill[i], flr[i][colour[id]])-have[i];
    }
  }
  if(currans.fi>ans.fi) ans=currans;
  else if(currans.fi==ans.fi) ans.se=min(ans.se, currans.se);
}

void gocolour(int color){
  for(int i=0; i<n; i++){
    int id=pltoid[i];
    if(colour[id]==color){
      find(id);
      i+=sz[id]-1;
    }
  }
}

void f() {
  cin >> n >> k;
  mxlvl=0;
  timer=0;
  ans={-1, -1};
  lvl.assign(n, 0);
  pa.assign(n, 0); for(int i=0; i<n; i++) pa[i]=i;
  colour.assign(n, 0);
  pl.assign(n, 0);
  sz.assign(n, 0);
  pltoid.assign(n, 0);
  flr.assign(0, vector<int>(0));
  cld.assign(n, vector<int>(0));
  for(int i=0; i<n; i++) cin >> colour[i];
  for(int i=1; i<n; i++){
    cin >> pa[i];
    cld[pa[i]].pb(i);
  }
  assign_lvl(0);
  mxlvl++;
  flr.assign(mxlvl, vector<int>(k, 0));
  for(int i=0; i<n; i++){
    flr[lvl[i]][colour[i]]++;
  }
  for(int i=0; i<k; i++){
    gocolour(i);
  }
  cout << ans.fi << ' ' << ans.se;
}

int main() {
  int tc = 1;
  // cin >> tc;
  for (int i = 1; i <= tc; i++) {
    // cout << endl << '#' << i << endl;
    f();
    cout << endl;
  }
}

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