Submission #1063430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063430		nima_aryan	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1103 ms	127668 KiB

bitaro

/**
 *    author:  NimaAryan
 *    created: 2024-08-17 20:59:09
**/
#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("O3,unroll-loops")

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

constexpr int SQ = 100;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int N, M, Q;
  cin >> N >> M >> Q;

  vector<vector<int>> g(N + 1);
  for (int i = 0; i < M; ++i) {
    int s, e;
    cin >> s >> e;
    --s, --e;
    g[e].push_back(s);
  }

  vector<vector<pair<int, int>>> f(N);
  bitset<100000> ex;
  for (int x = 0; x < N; ++x) {
    vector<pair<int, int>> cf{{ -1, x}};
    for (int y : g[x]) {
      cf.insert(cf.end(), f[y].begin(), f[y].end());
    }
    sort(cf.begin(), cf.end(), greater<>());
    vector<int> used;
    for (int i = 0; i < cf.size() && f[x].size() < SQ; ++i) {
      auto [d, s] = cf[i];
      d += 1;
      if (ex.test(s)) {
        continue;
      }
      used.push_back(s);
      ex.set(s);
      f[x].emplace_back(d, s);
    }
    for (int i : used) {
      ex.reset(i);
    }
  }

  vector<bool> ban(N);
  while (Q--) {
    int t, y;
    cin >> t >> y;
    --t;
    vector<int> C(y);
    for (int i = 0; i < y; ++i) {
      cin >> C[i];
      --C[i];
      ban[C[i]] = true;
    }
    if (y >= SQ) {
      vector<int> dp(t + 1);
      for (int x = 0; x <= t; ++x) {
        dp[x] = ban[x] ? -N : 0;
        for (int y : g[x]) {
          dp[x] = max(dp[x], dp[y] + 1);
        }
      }
      cout << max(-1, dp[t]) << "\n";
    } else {
      int ans = -1;
      for (auto [d, s] : f[t]) {
        if (!ban[s]) {
          ans = max(ans, d);
        }
      }
      cout << ans << "\n";
    }
    for (int i = 0; i < y; ++i) {
      ban[C[i]] = false;
    }
  }

  return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < cf.size() && f[x].size() < SQ; ++i) {
      |                     ~~^~~~~~~~~~~

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