제출 #1305307

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305307		alan_c	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	622 ms	210628 KiB

bitaro

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

const int N = 1e5 + 1, Y = 150;
int dp[N];
bitset<N> v;
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++) {
    priority_queue<array<int, 3>> pq;
    for (int j : adj[i])
      pq.emplace(array{best[j][0].first, j, 1});

    while (!pq.empty() && best[i].size() < Y) {
      auto [l, j, idx] = pq.top();
      pq.pop();

      int k = best[j][idx - 1].second;
      if (!v[k]) {
        best[i].emplace_back(l + 1, k);
        v[k] = true;
      }
      if (idx < (int)best[j].size())
        pq.emplace(array{best[j][idx].first, j, idx + 1});
    }

    for (auto &[l, j] : best[i])
      v[j] = false;

    if (best[i].size() < Y)
      best[i].emplace_back(0, i);
  }

  while (q--) {
    int t, y;
    cin >> t >> y;
    vector<int> c(y);
    for (int &i : c)
      cin >> i;

    int ans = -1;
    if (y < Y) {
      for (int i : c)
        v[i] = true;

      for (auto &[l, i] : best[t]) {
        if (!v[i]) {
          ans = l;
          break;
        }
      }

      for (int i : c)
        v[i] = false;
    } else {
      memset(dp, 0, sizeof(dp));
      for (int i : c)
        dp[i] = -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: 86 / 86