Submission #1092777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092777		vjudge1	Team Coding (EGOI24_teamcoding)	C++17	50 / 100	59 ms	26576 KiB

Main

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

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

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

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 = a[v].size() - 1, j = a[u].size() - 1; i >= 0; i--, j--) {
      a[u][j] += 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]]) {
      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]]) {
      int d = a[u].size() - 1 - (dep[v] - dep[u]);
      if (d >= 0 && d < a[u].size()) cnt[d] = 0;
    }
  }
}

void Dfs(int u, int co) {

}

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);
  for (int i = 1; i <= k; i++) {
    if (se[i].size() > MAXL) {

    }
  }
  cout << ans.first << ' ' << ans.second;
  return 0;
}

Compilation message (stderr)

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

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