Submission #928435

#	Time	Username	Problem	Language	Result	Execution time	Memory
928435		myst6	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2047 ms	5140 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100'000;
const int B = 320;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int N, M, Q;
  cin >> N >> M >> Q;
  vector<vector<int>> in(N);
  for (int i=0; i<M; i++) {
    int S, E;
    cin >> S >> E;
    S--, E--;
    in[E].push_back(S);
  }
  vector<vector<pair<int,int>>> dp(N);
  for (int i=0; i<N; i++) {
    set<pair<int,int>> S;
    for (int u : in[i]) {
      for (pair<int,int> p : dp[u]) {
        S.insert({p.first + 1, p.second});
      }
    }
    S.insert({0, i});
    int k = B;
    for (auto it = S.rbegin(); it != S.rend() && k > 0; ++it, --k) {
      dp[i].push_back(*it);
    }
  }
  for (int j=0; j<Q; j++) {
    int T, Y;
    cin >> T >> Y;
    T--;
    set<int> C;
    for (int i=0; i<Y; i++) {
      int c;
      cin >> c;
      C.insert(c-1);
    }
    if (Y < B) {
      bool ans = false;
      for (pair<int,int> p : dp[T]) {
        if (C.count(p.second) == 0) {
          cout << p.first << "\n";
          ans = true;
          break;
        }
      }
      if (!ans) {
        cout << "-1\n";
      }
    } else {
      vector<int> dp2(N, -1);
      dp2[T] = 0;
      for (int i=T; i>=0; i--) {
        if (dp2[i] == -1) continue;
        for (int u : in[i]) {
          dp2[u] = max(dp2[u], dp2[i] + 1);
        }
      }
      int ans = -1;
      for (int i=0; i<=T; i++) {
        if (dp2[i] > ans && C.count(i) == 0) ans = dp2[i];
      }
      cout << ans << "\n";
    }
  }
  return 0;
}

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