Submission #1305305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305305		alan_c	Bitaro’s Party (JOI18_bitaro)	C++20	14 / 100	2072 ms	97904 KiB

bitaro

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

const int N = 1e5 + 1, Y = 100;
int dp[N];
vector<int> adj[N];
vector<pair<int, int>> best[N];

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

  int n, m, q;
  cin >> n >> m >> q;
  while (m--) {
    int s, e;
    cin >> s >> e;
    adj[e].push_back(s);
  }

  for (int i = 1; i <= n; i++) {
    map<int, int> len = {{i, 0}};
    for (int j : adj[i])
      for (auto &[l, k] : best[j])
        len[k] = max(len[k], l + 1);

    best[i].reserve(len.size());
    for (auto &[j, l] : len)
      best[i].emplace_back(l, j);

    int size = min(Y, (int)len.size());
    nth_element(best[i].begin(), best[i].begin() + size - 1, best[i].end(),
                greater());
    best[i].erase(best[i].begin() + size, best[i].end());
    sort(best[i].begin(), best[i].end(), greater());
  }

  while (q--) {
    int t, y;
    cin >> t >> y;

    int ans = -1;
    if (y < Y) {
      set<int> busy;
      while (y--) {
        int c;
        cin >> c;
        busy.insert(c);
      }

      for (auto &[l, i] : best[t]) {
        if (!busy.count(i)) {
          ans = l;
          break;
        }
      }
    } else {
      memset(dp, 0, sizeof(dp));
      while (y--) {
        int c;
        cin >> c;
        dp[c] = -1;
      }

      for (int i = 1; i <= t; i++)
        for (int j : adj[i])
          if (dp[j] != -1)
            dp[i] = max(dp[i], dp[j] + 1);

      ans = dp[t];
    }
    cout << ans << '\n';
  }
}

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