Submission #1092772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092772		vjudge1	Team Coding (EGOI24_teamcoding)	C++17	100 / 100	239 ms	30536 KiB

Main

#include<bits/stdc++.h>

using namespace std;
using pir = pair<int, int>;

const int K = 1320;
const int inf = 1316;
const int N = 1e5 + 5;

pir ans;
vector<pir> s[N];
vector<int> joke, g[N], c[N];
int n, k, id, dd[N], l[N], r[N], ccme[N], sum[N], col[N], dep[N], dfn[N], cnt[N], siz[N];

pir getmx(pir a, pir b){
  if(a.first > b.first) return a;
  else if(a.first < b.first) return b;
  else if(a.second < b.second) return a;
  return b;
}

void dfs(int x, int fa){
  dep[x] = dep[fa] + 1;
  dfn[x] = ++id;
  c[col[x]].push_back(x);
  for(int v : g[x]){
    if(v != fa){
      dfs(v, x);
    }
  }
}

void DFS(int x, int fa, int op){
  cnt[dep[x]] += (col[x] == op);
  siz[x] += (col[x] == op);
  for(int v : g[x]){
    if(v != fa){
      DFS(v, x, op);
      siz[x] += siz[v];
    }
  }
}

void DDFS(int x, int fa, int op){
  s[x].clear();
  int maxx = -1, h = 0;
  for(int v : g[x]){
    if(v != fa){
      DDFS(v, x, op);
      if(r[v] > maxx){
        maxx = r[v], h = v;
      }
    }
  }
  if(h) swap(s[x], s[h]), swap(l[x], l[h]), swap(r[x], r[h]), swap(sum[x], sum[h]);
  s[x].push_back({dep[x], 1});
  sum[x] += min(cnt[dep[x]], 1);
  l[x] = dep[x], r[x] = max(r[x], dep[x]);
  for(int v : g[x]){
    if(v != fa && v != h){
      for(pir num : s[v]){
        int now = s[x].size() - 1 - (num.first - dep[x]);
        int tmp = min(cnt[num.first], s[x][now].second);
        s[x][now].second += num.second;
        sum[x] += min(cnt[num.first], s[x][now].second) - tmp;
      }
    }
  }
  if(col[x] == op) ans = getmx(ans, {sum[x], sum[x] - siz[x]});
}

void DDDFS(int x, int fa){
  s[x].clear();
  siz[x] = 1;
  int maxx = -1, h = 0;
  for(int v : g[x]){
    if(v != fa){
      DDDFS(v, x);
      siz[x] += siz[v];
      if(r[v] > maxx){
        maxx = r[v], h = v;
      }
    }
  }
  if(h) swap(s[x], s[h]), swap(l[x], l[h]), swap(r[x], r[h]);
  s[x].push_back({dep[x], 1});
  l[x] = dep[x], r[x] = max(r[x], dep[x]);
  for(int v : g[x]){
    if(v != fa && v != h){
      for(pir num : s[v]){
        int now = s[x].size() - 1 - (num.first - dep[x]);
        int tmp = min(cnt[num.first], s[x][now].second);
        s[x][now].second += num.second;
      }
    }
  }
  if(ccme[col[x]] < inf){
    int jian = 0;
    int sum = 0;
    for(int v : c[col[x]]) dd[dep[v]] = 0;
    for(int v : c[col[x]]){
      if(dfn[v] >= dfn[x] && dfn[v] <= dfn[x] + siz[x] - 1){
        jian++;
      }
      dd[dep[v]]++;
    }
    for(int v : c[col[x]]){
      if(dd[dep[v]] && dep[v] >= l[x] && dep[v] <= r[x]){
        int now = s[x].size() - 1 - (dep[v] - l[x]);
        sum += min(dd[dep[v]], s[x][now].second);
        dd[dep[v]] = 0;
      }
    }
    ans = getmx(ans, {sum, sum - jian});
  }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> k;
  for(int i = 1; i <= n; i++){
    cin >> col[i];
    ccme[col[i]]++;
  }
  for(int i = 2, f; i <= n; i++){
    cin >> f;
    g[++f].push_back(i);
  }
  for(int i = 0; i <= k; i++){
    if(ccme[i] >= inf){
      joke.push_back(i);
    }
  }
  ans.first = -1;
  dfs(1, 0);
  for(int i = 1; i <= n; i++) s[i].clear();
  for(int v : joke){
    for(int i = 1; i <= n; i++) cnt[i] = 0, siz[i] = 0, sum[i] = 0, l[i] = 0, r[i] = 0;
    for(int i = 1; i <= n; i++) s[i].clear();
    DFS(1, 0, v);
    DDFS(1, 0, v);
  }
  for(int i = 1; i <= n; i++) l[i] = 0, r[i] = 0, siz[i] = 0, s[i].clear();
  DDDFS(1, 0);
  cout << ans.first << ' ' << ans.second;
  return 0;
}
/*
合并子树内有多少个深度为 i 的点
对于每种颜色：
1. 拥有颜色数量 <= sqrt(n)，只需关注需要关注的
2. 大于 sqrt(n)，对于每种颜色单独考虑
*/

Compilation message (stderr)

Main.cpp: In function 'void DDDFS(int, int)':
Main.cpp:92:13: warning: unused variable 'tmp' [-Wunused-variable]
   92 |         int tmp = min(cnt[num.first], s[x][now].second);
      |             ^~~

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