제출 #128883

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
128883		RockyB	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2047 ms	9720 KiB

bitaro

// In The Name Of The God

#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()

#define rep(a, b, c) for (int (a) = (b); (a) <= (c); a++) 
#define per(a, b, c) for (int (a) = (b); (a) >= (c); a--) 

#define nl '\n'
#define ioi exit(0);

using namespace std;

const int MAX_N = (int)1e5 + 7;
const int K = 1000;
const int inf = (int)1e9 + 7;

int n, m, q;
vector <int> g[MAX_N];

int T, k;
int tmr;
int a[MAX_N], was[MAX_N], dp[MAX_N], h[MAX_N];
bool ban[MAX_N];

int calc(int v) {
  int res = -inf;
  if (was[v] == tmr) return dp[v];
  was[v] = tmr;
  if (!ban[v]) res = 0;
  for (auto to : g[v]) {
    res = max(res, calc(to) + 1);
  }
  return dp[v] = res;
}
void read() {
  cin >> T >> k;
  rep(i, 1, k) {
    cin >> a[i];
  }
}
void naive() {
  rep(i, 1, k) {
    ban[a[i]] = 1;
  }  
  ++tmr;
  int res = calc(T);
  if (res < 0) res = -1;
  cout << res << nl;
  rep(i, 1, k) {
    ban[a[i]] = 0;
  }  
}
int sz[MAX_N], used[MAX_N];
pair <int, int> bfr[MAX_N];
pair <int, int> dist[MAX_N][K];
void pre() {
  rep(i, 1, n) {
    int S = 0;
    bfr[S++] = {0, i};
    for (auto to : g[i]) {
      for (int j = 0; j < sz[to]; j++) {
        auto it = dist[to][j];
        bfr[S++] = {it.f + 1, it.s};
      }
    }
    /* cerr << S << nl;
    continue;
    for (int j = 0; j < S; j++) cerr << bfr[j].f << ' ' << bfr[j].s << nl; */
    sort(bfr, bfr + S, greater < pair <int, int> > () );
    /* cerr << "check->";
    for (int j = 0; j < S; j++) cerr << bfr[j].f << ' ' << bfr[j].s << nl;
    continue */;
    rep(j, 0, S - 1) {
      if (used[bfr[j].s] == i) continue;
      if (sz[i] < K) {
        used[bfr[j].s] = i;
        dist[i][sz[i]++] = bfr[j];
      }
      else break;
    }
  }
  /* rep(i, 1, n) {
    cerr << i << " -> ";
    rep(j, 0, sz[i] - 1) cerr << dist[i][j].s << ' ';
    cerr << nl;
  } */
}
void fast() {
  int res = -1;
  rep(i, 1, k) {
    ban[a[i]] = 1;
  }
  rep(i, 0, sz[T] - 1) {
    if (!ban[dist[T][i].s]) {
      res = max(res, dist[T][i].f);
      break;
    }
  }
  rep(i, 1, k) {
    ban[a[i]] = 0;
  }
  cout << res << nl;
  //cerr << "DA\n";
}
int main() {
  ios_base :: sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  #ifdef IOI
    freopen ("in.txt", "r", stdin);
    freopen ("B.out", "w", stdout);
  #endif
  cin >> n >> m >> q;
  rep(i, 1, m) {
    int s, e;
    cin >> s >> e;
    g[e].pb(s);
  }
  //rep(i, 1, n) for (auto to : g[i]) if (!to) assert(0);
  pre();
  //for (auto it : st[2]) cerr << it.f << ' ' << it.s << nl;
  
  rep(i, 1, q) {
    read();
    fast();
    continue;
    if (k >= K || T <= K) naive();
    else fast();
  }
  ioi
}

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