Submission #201995

#	Time	Username	Problem	Language	Result	Execution time	Memory
201995		EntityIT	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1838 ms	421220 KiB

bitaro

#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

template<class T>
inline bool asMn(T &a, const T &b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T &a, const T &b) { return a < b ? a = b, true : false; }

const int bdr = 400;
mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() );

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  #ifdef FourLeafClover
  freopen("input", "r", stdin);
  #endif // FourLeafCLover

  int n, m, q; cin >> n >> m >> q;

  vector<vector<int> > gr(n);
  while (m--) {
    int s, e; cin >> s >> e; --s; --e;
    gr[e].emplace_back(s);
  }

  vector<vector<pair<int, int> > > d(n);
  vector<int> val(n, -1), wait;
  for (int u = 0; u < n; ++u) {
    for (int v : gr[u]) {
      for (auto _ : d[v]) {
        if (val[_.second] == -1) wait.emplace_back(_.second);
        asMx(val[_.second], _.first + 1);
      }
    }
    asMx(val[u], 0);
    wait.emplace_back(u);

    nth_element(wait.begin(), wait.begin() + min(bdr, sz(wait) ), wait.end(), [&](int i, int j) { return val[i] > val[j]; });
    for (int i = 0; i < min(bdr, sz(wait) ); ++i) d[u].emplace_back(pair<int, int>{ val[ wait[i] ], wait[i] } );
    for (int v : wait) val[v] = -1;
    wait.clear();
  }

  vector<int> f(n, -1);
  vector<bool> banned(n, false);
  function<int(int)> F = [&](int u) {
    if (~f[u]) return f[u];
    f[u] = (banned[u] ? -2 : 0);
    for (int v : gr[u]) if (F(v) >= 0) asMx(f[u], f[v] + 1);
    return f[u];
  };

  while (q--) {
    int t, y; cin >> t >> y; --t;
    vector<int> tmp(y);
    for (auto &u : tmp) {
      cin >> u; --u;
      banned[u] = true;
    }

    if (y >= bdr) {
      cout << max(F(t), -1) << '\n';
      f.assign(n, -1);
    }
    else {
      int ans = -1;
      for (auto _ : d[t]) if (!banned[_.second]) asMx(ans, _.first);
      cout << ans << '\n';
    }

    for (int u : tmp) banned[u] = false;
  }

  return 0;
}

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