제출 #1322364

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1322364		campos	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	11 ms	6480 KiB

bitaro

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <class T>
using ord_set = tree<T, null_type, less<T>, rb_tree_tag,
tree_order_statistics_node_update>;

#define int long long
#define all(x) x.begin(), x.end()
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)
#define len(a) ((int)a.size())

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

const int INF = 0x3f3f3f3f3f3f3f3f;

void solution() {
  int n, m, q;
  cin >> n >> m >> q;

  vector<int> adj[n];
  vector<int> value(n);
  for(int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u -= 1, v -= 1;
    adj[u].emplace_back(v);
    value[v] += 1;
  }

  queue<int> Q;
  for(int i = 0; i < n; i++) {
    if(!value[i]) Q.push(i);
  }

  vector<int> ord;
  while(Q.size()) {
    int u = Q.front(); Q.pop();
    ord.emplace_back(u);
    for(int v : adj[u]) {
      value[v] -= 1;
      if(!value[v]) Q.push(v);
    }
  }

  int root = sqrt(n) + 100;

  vector<pair<int,int>> dp[n];
  vector<bool> used(n);

  for(auto u : ord) {
    vector<pair<int,int>> ndp;

    dp[u].emplace_back(0, u);

    sort(all(dp[u]), greater<>());

    for(auto [l, v] : dp[u]) {
      if(used[v]) continue;
      used[v] = 1;
      ndp.emplace_back(l, v);
    }

    dp[u] = ndp;

    for(auto [l, v] : dp[u]) {
      used[v] = 0;
    }

    while(len(dp[u]) > root) dp[u].pop_back();

    for(auto v : adj[u]) {
      for(auto [x, y] : dp[u]) {
        dp[v].emplace_back(x + 1, y);
      }
    }
  }

  vector<bool> cant(n);
  while(q--) {
    int t, y;
    cin >> t >> y;
    t -= 1;

    vector<int> c(y);
    for(int i = 0; i < y; i++) {
      cin >> c[i];
      c[i] -= 1;
      cant[c[i]] = 1;
    }

    if(y >= root) {
      vector<int> ndp(n, -INF);
      for(auto u : ord) {
        if(!cant[u]) {
          chmax(ndp[u], 0LL);
        }
        for(auto v : adj[u]) {
          chmax(ndp[v], ndp[u] + 1);
        }
      }
      cout << (ndp[t] == -INF ? -1LL : ndp[t]) << "\n";
    }
    else {
      int ans = -1;
      for(auto [l, u] : dp[t]) {
        if(!cant[u]) {
          ans = l;
          break;
        }
      }
      cout << ans << "\n";
    }

    for(int i = 0; i < y; i++) {
      cant[c[i]] = 0;
    }
  }
}

/*
 * LE O PROBLEMA ATE O FINAL
 * LE OS SAMPLES, ENTENDE OS SAMPLES
 * LE INPUT, LE OUTPUT
 * LE OS CONSTRAINTS
 */

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tt = 1;
  while(tt--) {
    solution();
  }
  return 0;
}

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