Submission #623902

#	Time	Username	Problem	Language	Result	Execution time	Memory
623902		ipaljak	Tax Evasion (LMIO19_mokesciai)	C++14	100 / 100	299 ms	49324 KiB

mokesciai

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 10;
const int LOGN = 19;

vector<int> v[MAXN];

int n, m, tick;
int dsc[MAXN], fin[MAXN], lvl[MAXN], dad[MAXN][LOGN];

inline pair<int, int> maxp(const pair<int, int> &a, const pair<int, int> &b) {
  if (a > b) return a;
  return b;
}

struct Tournament {
  int offset;
  vector<pair<int, int>> t;

  Tournament(int sz) {
    for (offset = 1; offset <= sz; offset *= 2);
    t.resize(2 * offset);
  }

  void ins(int i, int val) {
    i += offset; t[i] = {val, i - offset};
    for (i /= 2; i > 0; i /= 2)
      t[i] = maxp(t[2 * i], t[2 * i + 1]);
  }

  pair<int, int> max(int node, int from, int to, int lo, int hi) {
    if (to <= lo || hi <= from) return {-1, -1};
    if (from >= lo && to <= hi) return t[node];
    return maxp(max(2 * node, from, (from + to) / 2, lo, hi),
                max(2 * node + 1, (from + to) / 2, to, lo, hi));
  }

  pair<int, int> max(int lo, int hi) {
    return max(1, 0, offset, lo, hi);
  }
};

inline void init() {
  for (int j = 1; j < LOGN; ++j)
    for (int i = 0; i < n; ++i)
      dad[i][j] = dad[dad[i][j - 1]][j - 1];
}

void dfs(int node, int l) {
  ++tick;
  dsc[node] = tick;
  lvl[node] = l;
  for (int nxt : v[node]) {
    if (nxt == dad[node][0]) continue;
    dfs(nxt, l + 1);
  }
  fin[node] = tick;
}

int up(int node, int k) {
  for (int j = LOGN - 1; j >= 0; --j) {
    if ((1 << j) <= k) {
      node = dad[node][j];
      k -= 1 << j;
    }
  }
  return node;
}

int main(void) {
  scanf("%d%d", &n, &m);
  for (int i = 1; i < n; ++i) {
    scanf("%d", &dad[i][0]);
    --dad[i][0];
    v[dad[i][0]].push_back(i);
  }

  init();
  dfs(0, 0);

  vector<pair<int, int>> I;
  for (int i = 0; i < m; ++i) {
    int x;
    scanf("%d", &x); --x;
    x = up(x, (lvl[x] - 1) / 2);
    I.emplace_back(dsc[x], fin[x]);
  }

  sort(I.begin(), I.end(),
       [&](const pair<int, int> &A, const pair<int, int> &B) {
         return A.second - A.first < B.second - B.first;
       });

  Tournament T(n + 10);
  for (int i = 0; i < n; ++i)
    T.ins(dsc[i], lvl[i]);

  int sol = n + 10;
  for (const auto &p : I) {
    auto mx = T.max(p.first, p.second + 1);
    sol = min(sol, mx.first);
    T.ins(mx.second, 0);
  }

  printf("%d\n", sol + 1);
  return 0;
}

Compilation message (stderr)

mokesciai.cpp: In function 'int main()':
mokesciai.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
mokesciai.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     scanf("%d", &dad[i][0]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
mokesciai.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |     scanf("%d", &x); --x;
      |     ~~~~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 39 / 39
• Subtask 4: 29 / 29