Submission #807680

#	Time	Username	Problem	Language	Result	Execution time	Memory
807680		dong_liu	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	490 ms	166916 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

using LL = long long;
const int N = 100000, B = 200, Q = 100000, INF = 0x3f3f3f3f;

vector<int> gr[N];
pair<int, int> pp[N][B];

void join(pair<int, int> *aa, pair<int, int> *bb, pair<int, int> *cc) {
  static int used[N], _ = 1;

  int i = 0, j = 0;

  for (int k = 0; k < B; k++) {
    while (i < B && aa[i].second != -1 && used[aa[i].second] == _) i++;
    while (j < B && bb[j].second != -1 && used[bb[j].second] == _) j++;
    if (i == B)
      cc[k] = {bb[j].first + 1, bb[j].second}, j++;
    else if (j == B)
      cc[k] = aa[i++];
    else if (aa[i].first > bb[j].first + 1)
      cc[k] = aa[i++];
    else
      cc[k] = {bb[j].first + 1, bb[j].second}, j++;
    if (cc[k].second != -1) used[cc[k].second] = _;
  }
  _++;
}

void run() {
  int n, m, q;

  scanf("%d%d%d", &n, &m, &q);
  while (m--) {
    int i, j;

    scanf("%d%d", &i, &j), i--, j--;
    gr[j].push_back(i);
  }
  for (int i = 0; i < n; i++) {
    static pair<int, int> tmp[B];

    for (int j = 0; j < B; j++) pp[i][j] = {-INF, -1};
    pp[i][0] = {0, i};
    for (int j : gr[i]) {
      join(pp[i], pp[j], tmp);
      for (int k = 0; k < B; k++) pp[i][k] = tmp[k];
    }
  }
  for (int h = 1; h <= q; h++) {
    static int removed[N];
    int i, k, ans = -1;

    scanf("%d%d", &i, &k), i--;
    for (int _ = 0; _ < k; _++) {
      int j;

      scanf("%d", &j), j--;
      removed[j] = h;
    }
    if (k < B) {
      for (int _ = 0; _ < B; _++) {
        auto [d, j] = pp[i][_];

        if (j == -1) break;
        if (removed[j] != h) {
          ans = d;
          break;
        }
      }
    } else {
      static int dd[N];

      memset(dd, -0x3f, n * sizeof *dd);
      dd[i] = 0;
      for (int j = i; j >= 0; j--) {
        int d = dd[j];

        if (d == -INF) continue;
        if (removed[j] != h) ans = max(ans, d);
        for (int k : gr[j]) dd[k] = max(dd[k], d + 1);
      }
    }
    printf("%d\n", ans);
  }
}

int main() {
  run();
  return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void run()':
bitaro.cpp:34:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |   scanf("%d%d%d", &n, &m, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d%d", &i, &j), i--, j--;
      |     ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%d%d", &i, &k), i--;
      |     ~~~~~^~~~~~~~~~~~~~~~
bitaro.cpp:59:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |       scanf("%d", &j), j--;
      |       ~~~~~^~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 86 / 86