Submission #1063412

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

bitaro

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

using namespace std;

#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);
  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<>());
    unordered_set<int> ex;
    for (int i = 0; i < cf.size() && f[x].size() < SQ; ++i) {
      auto [d, s] = cf[i];
      d += 1;
      if (ex.count(s)) {
        continue;
      }
      ex.insert(s);
      f[x].emplace_back(d, s);
    }
  }

  while (Q--) {
    int t, y;
    cin >> t >> y;
    --t;
    unordered_set<int> ex;
    for (int i = 0; i < y; ++i) {
      int c;
      cin >> c;
      --c;
      ex.insert(c);
    }
    if (y >= SQ) {
      vector<int> dp(t + 1);
      for (int x = 0; x <= t; ++x) {
        dp[x] = ex.count(x) ? -N : 0;
        for (int y : g[x]) {
          dp[x] = max(dp[x], dp[y] + 1);
        }
      }
      cout << max(-1, dp[t]) << "\n";
      continue;
    }
    int ans = -1;
    for (auto [d, s] : f[t]) {
      if (!ex.count(s)) {
        ans = max(ans, d);
      }
    }
    cout << ans << "\n";
  }

  return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:40: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]
   40 |     for (int i = 0; i < cf.size() && f[x].size() < SQ; ++i) {
      |                     ~~^~~~~~~~~~~

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