Submission #853774

#	Time	Username	Problem	Language	Result	Execution time	Memory
853774		NeroZein	Bitaro’s Party (JOI18_bitaro)	C++17	14 / 100	619 ms	410712 KiB

bitaro

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

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int B = 450;
const int N = 1e5 + 5;

using T = pair<int, int>;

bool in[N]; 
bool blocked[N];
vector<int> rg[N];
vector<T> furthest[N]; //desceding on second

inline vector<T> merge(const vector<T>& x, const vector<T>& y) {
  vector<T> ret;
  int i = 0, j = 0;
  int n = (int) x.size(), m = (int) y.size();
  while ((int) ret.size() < B && (i < n || j < m)) {
    if (i == n || (j < m && x[i].second <= y[j].second)) {
      if (!in[y[j].first]) {
        in[y[j].first] = 1; 
        ret.push_back(y[j]); 
        ret.back().second++;
      }
      j++; 
    } else {
      if (!in[x[i].first]) {
        in[x[i].first] = 1;
        ret.push_back(x[i]);
      }
      i++; 
    }
  }
  for (int k = 0; k < (int) ret.size(); ++k) {
    in[ret[k].first] = 0; 
  }
  return ret;
}

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, m, q;
  cin >> n >> m >> q; 
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    rg[v].push_back(u); 
  }
  for (int i = 1; i <= n; ++i) {
    for (int j : rg[i]) {
      furthest[i] = merge(furthest[i], furthest[j]); 
    }
    furthest[i].emplace_back(i, 0);
  }
  auto run_dp = [&](int v) {
    vector<int> max_cost(n + 1, -1); 
    for (int i = 1; i <= n; ++i) {
      if (!blocked[i]) {
        max_cost[i] = 0; 
      }
      for (int j : rg[i]) {
        if (max_cost[j] != -1) {
          max_cost[i] = max(max_cost[i], max_cost[j] + 1); 
        }
      }
    }
    return max_cost[v];
  };
  while (q--) {
    int v, b;
    cin >> v >> b;
    vector<int> qv(b); 
    for (int i = 0; i < b; ++i) {
      cin >> qv[i];
      blocked[qv[i]] = true; 
    }
    if (b == (int) furthest[v].size() && (int) furthest[v].size() < B - 5) {
      cout << -1 << '\n'; 
    } else if (b < B) {
      bool f = false;
      for (auto [u, d] : furthest[v]) {
        if (!blocked[u]) {
          f = true; 
          cout << d << '\n';
          break; 
        }
      }
      if (!f) {
        cout << -1 << '\n'; 
      }
    } else {
      cout << run_dp(v) << '\n'; 
    }
    for (int i = 0; i < b; ++i) {
      blocked[qv[i]] = false; 
    }
  }
  return 0;
}

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