oj.uz

Submission #1092771

# Submission time Handle Problem Language Result Execution time Memory
1092771 2024-09-25T03:00:03 Z vjudge1 Team Coding (EGOI24_teamcoding) C++17
0 / 100
 63 ms 27088 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 3 ms 7316 KB Output is correct
3 Correct 3 ms 7512 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 5 ms 7516 KB Output is correct
6 Correct 3 ms 7516 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 4 ms 7772 KB Output is correct
9 Correct 40 ms 26812 KB Output is correct
10 Correct 3 ms 7512 KB Output is correct
11 Correct 8 ms 7772 KB Output is correct
12 Incorrect 26 ms 24864 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 3 ms 7516 KB Output is correct
4 Correct 8 ms 7772 KB Output is correct
5 Incorrect 28 ms 24776 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 3 ms 7516 KB Output is correct
3 Correct 4 ms 7516 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 3 ms 7516 KB Output is correct
6 Correct 3 ms 7516 KB Output is correct
7 Correct 3 ms 7540 KB Output is correct
8 Correct 63 ms 26832 KB Output is correct
9 Correct 3 ms 7516 KB Output is correct
10 Correct 3 ms 7776 KB Output is correct
11 Correct 47 ms 27088 KB Output is correct
12 Incorrect 3 ms 7516 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7524 KB Output is correct
2 Correct 4 ms 7384 KB Output is correct
3 Correct 3 ms 7524 KB Output is correct
4 Correct 4 ms 7524 KB Output is correct
5 Correct 3 ms 7528 KB Output is correct
6 Correct 4 ms 7528 KB Output is correct
7 Correct 4 ms 7532 KB Output is correct
8 Correct 3 ms 7784 KB Output is correct
9 Correct 3 ms 7528 KB Output is correct
10 Correct 8 ms 7784 KB Output is correct
11 Correct 3 ms 7528 KB Output is correct
12 Correct 3 ms 7820 KB Output is correct
13 Correct 3 ms 7528 KB Output is correct
14 Incorrect 3 ms 7528 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7516 KB Output is correct
2 Correct 3 ms 7316 KB Output is correct
3 Correct 3 ms 7512 KB Output is correct
4 Correct 3 ms 7516 KB Output is correct
5 Correct 5 ms 7516 KB Output is correct
6 Correct 3 ms 7516 KB Output is correct
7 Correct 3 ms 7516 KB Output is correct
8 Correct 4 ms 7772 KB Output is correct
9 Correct 40 ms 26812 KB Output is correct
10 Correct 3 ms 7512 KB Output is correct
11 Correct 8 ms 7772 KB Output is correct
12 Incorrect 26 ms 24864 KB Output isn't correct
13 Halted 0 ms 0 KB -