Submission #789282

#	Time	Username	Problem	Language	Result	Execution time	Memory
789282		tch1cherin	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1442 ms	415040 KiB

bitaro

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

const int MAX_N = 1e5 + 5;
const int K = 320;
vector<int> G[MAX_N];
vector<pair<int, int>> values[MAX_N];
int max_value[MAX_N], dp[MAX_N] = {};
bool vis[MAX_N] = {}, used[MAX_N] = {};
vector<int> order;

void topsort(int u) {
  vis[u] = true;
  for (int v : G[u]) {
    if (!vis[v]) {
      topsort(v);
    }
  }
  order.push_back(u);
}

void DFS(int u) {
  vis[u] = true;
  for (int v : G[u]) {
    if (!vis[v]) {
      DFS(v);
    }
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, M, Q;
  cin >> N >> M >> Q;
  for (int i = 0; i < M; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    G[v].push_back(u);
  }
  order.reserve(N);
  for (int i = 0; i < N; i++) {
    if (!vis[i]) {
      topsort(i);
    }
  }
  memset(max_value, -1, sizeof max_value);
  for (int i : order) {
    values[i] = {{0, i}};
    for (int j : G[i]) {
      vector<int> vals;
      for (auto [val, v] : values[i]) {
        vals.push_back(v);
        max_value[v] = -val;
      }
      for (auto [val, v] : values[j]) {
        if (max_value[v] == -1) {
          vals.push_back(v);
        }
        max_value[v] = max(max_value[v], -val + 1);
      }
      values[i] = vector<pair<int, int>>();
      for (int p : vals) {
        values[i].push_back({-max_value[p], p});
      }
      if (values[i].size() > K) {
        nth_element(values[i].begin(), values[i].begin() + K, values[i].end());
        values[i].resize(K);
      }
      for (int p : vals) {
        max_value[p] = -1;
      }
    }
  } 
  for (int q = 0; q < Q; q++) {
    int T, Y;
    cin >> T >> Y;
    T--;
    vector<int> C(Y);
    for (int &v : C) {
      cin >> v;
      used[--v] = true;
    }
    if (Y < K) {
      int ans = -1;
      for (auto [val, v] : values[T]) {
        ans = -val > ans && !used[v] ? -val : ans;
      }
      cout << ans << "\n";
    } else {
      memset(dp, -1, sizeof dp);
      for (int i : order) {
        if (!used[i]) {
          dp[i] = 0;   
        }
        for (int j : G[i]) {
          if (dp[j] != -1) {
            dp[i] = dp[j] + 1 > dp[i] ? dp[j] + 1 : dp[i]; 
          }
        }
      }
      cout << dp[T] << "\n";
    }
    for (int v : C) {
      used[v] = false;
    }
  }
}

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