Submission #1092771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092771		vjudge1	Team Coding (EGOI24_teamcoding)	C++17	0 / 100	63 ms	27088 KiB

Main

#include <iostream>
#include <vector>
#include <queue>

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

const int MAXN = 1e5 + 5, MAXL = 1900;

pii ans = {-1, MAXN};
vector<int> g[MAXN], a[MAXN], se[MAXN];
int n, k, tot, dfn[MAXN], b[MAXN], co[MAXN], dep[MAXN], cnt[MAXN];

void init(int u) {
  b[u] = dfn[u] = ++tot;
  for (auto v : g[u]) {
    dep[v] = dep[u] + 1;
    init(v), b[u] = b[v];
  }
}

void Max(int c, int k) {
  if (ans.first < c || (c == ans.first && ans.second > k)) {
    ans = {c, k};
  }
}

void dfs(int u) {
  for (auto v : g[u]) {
    dfs(v);
    if (a[u].size() < a[v].size()) {
      swap(a[u], a[v]);
    }
    for (int i = 0; i < a[v].size(); i++) {
      a[u][i] += a[v][i];
    }
  }
  a[u].push_back(1);
  if (se[co[u]].size() <= MAXL) {
    int c = 0, k = 0;
    for (auto v : se[co[u]]) {
      //cout << v << ' ';
      int d = a[u].size() - 1 - (dep[v] - dep[u]);
      k += (dfn[v] >= dfn[u] && dfn[v] <= b[u]);
      if (d >= 0 && d < a[u].size() && cnt[d] < a[u][d]) {
        cnt[d]++, c++;
      }
    }
    Max(c, c - k);
    for (auto v : se[co[u]]) {
      cnt[a[u].size() - 1 - (dep[v] - dep[u])] = 0;
    }
    //cout << u << ' ' << c << ' ' << k << '\n';
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    cin >> co[i], se[co[i]].push_back(i);
  }
  for (int i = 1, fa; i < n; i++) {
    cin >> fa, g[fa].push_back(i);
  }
  init(0), dfs(0);
  cout << ans.first << ' ' << ans.second;
  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void dfs(int)':
Main.cpp:34:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i = 0; i < a[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
Main.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |       if (d >= 0 && d < a[u].size() && cnt[d] < a[u][d]) {
      |                     ~~^~~~~~~~~~~~~

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