제출 #1193935

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1193935		veehj	Team Coding (EGOI24_teamcoding)	C++20	0 / 100	541 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, place;
pair<int, int> tans;
vector<int> l, pa, sz, lvl, pl;
vector<vector<int>> child;
/**cnt[level][colour][?]=pre*/
vector<vector<vector<int>>> cnt; 

int count(int id, int level, int colour){
  int ret=cnt[level][colour][pl[id]+sz[id]-1];
  if(pl[id]>0) ret-=cnt[level][colour][pl[id]-1];
  return ret;
}

void ifme(int id){
  pair<int, int> ans={0, 0};
  rep(level, lvl[id]+1, mxlvl+1){
    ll canfill=count(id, level, k), haveinside=count(id, level, l[id]), thislevel=cnt[level][l[id]][n-1];
    canfill=min(canfill, thislevel);
    ans.fi+=canfill;
    ans.se+=canfill-haveinside;
  }
  ans.fi++;
  if(tans.fi==-1) tans=ans;
  if(tans.fi<ans.fi){
    tans=ans;
  } else if(tans.fi==ans.fi){
    tans.se=min(tans.se, ans.se);
  }
}

void prerun(int x){
  pl[x]=place;
  place++;
  mxlvl=max(mxlvl, lvl[x]);
  for(auto& u : child[x]){
    lvl[u]=lvl[x]+1;
    prerun(u);
    sz[x]+=sz[u];
  }
}

void f() {
  cin >> n >> k;
  mxlvl=0;
  place=0;
  tans={-1, -1};
  l.resize(n);
  pa.resize(n);
  sz.assign(n, 1);
  lvl.assign(n, 0);
  pl.assign(n, 0);
  child.assign(n, vector<int>(0));
  cnt={};
  for(auto& u : l) cin >> u;
  rep(i, 1, n){
    ll x; cin >> x;
    pa[i]=x;
    child[x].pb(i);
  }
  lvl[0]=0;
  prerun(0);
  cnt.assign(mxlvl+1, vector<vector<int>>(k+1, vector<int>(n, 0)));
  //cnt[level][l][?]=pre
  rep(i, 0, n){
    cnt[lvl[i]][l[i]][pl[i]]++;
    cnt[lvl[i]][k][pl[i]]++;
  }
  rep(level, 0, mxlvl+1){
    rep(colour, 0, k+1){
      rep(i, 1, n) cnt[level][colour][i]+=cnt[level][colour][i-1];
    }
  }
  rep(i, 0, n){
    ifme(i);
  }
  cout << tans.fi << ' ' << tans.se;
}

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

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