Submission #928442

#	Time	Username	Problem	Language	Result	Execution time	Memory
928442		myst6	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1940 ms	415456 KiB

bitaro

#include <bits/stdc++.h>

using namespace std;

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

int main() {
  auto t1 = chrono::high_resolution_clock::now();
  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);
  vector<bool> used(N);
  for (int i=0; i<N; i++) {
    priority_queue<array<int,3>> nxt;
    for (int u : in[i]) {
      nxt.push({dp[u][0].first, u, 0});
    }
    while (dp[i].size() < B && !nxt.empty()) {
      array<int,3> a = nxt.top();
      nxt.pop();
      int root = dp[a[1]][a[2]].second;
      if (!used[root]) {
        used[root] = 1;
        dp[i].push_back({a[0]+1, root});
      }
      if (a[2] + 1 < dp[a[1]].size()) {
        nxt.push({dp[a[1]][a[2]+1].first, a[1], a[2]+1});
      }
    }
    for (pair<int,int> p : dp[i]) {
      used[p.second] = 0;
    }
    if (dp[i].size() < B) {
      dp[i].push_back({0, i});
    }
  }
  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";
    }
  }
  auto t2 = chrono::high_resolution_clock::now();
  //cout << chrono::duration_cast<chrono::milliseconds>(t2-t1).count() << "ms\n";
  return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:35:20: warning: comparison of integer expressions of different signedness: 'std::array<int, 3>::value_type' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |       if (a[2] + 1 < dp[a[1]].size()) {
bitaro.cpp:9:8: warning: variable 't1' set but not used [-Wunused-but-set-variable]
    9 |   auto t1 = chrono::high_resolution_clock::now();
      |        ^~
bitaro.cpp:84:8: warning: variable 't2' set but not used [-Wunused-but-set-variable]
   84 |   auto t2 = chrono::high_resolution_clock::now();
      |        ^~

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