Submission #964609

#	Time	Username	Problem	Language	Result	Execution time	Memory
964609		abczz	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1270 ms	273596 KiB

bitaro

#include <iostream>
#include <vector>
#include <array>
#include <queue>
#define ll int

using namespace std;

vector <ll> adj[100000];
priority_queue <array<ll, 3>> pq;
queue <ll> Q;
array <ll, 2> dp[100000][330];
ll n, m, q, a, k, b, f, rt = 200, dist[100000], B[100000], in[100000], visited[100000], ver[100000];

void dfs(ll u) {
  visited[u] = q;
  dist[u] = in[u] = 0;
  for (auto v : adj[u]) {
    if (visited[v] != q) dfs(v);
    ++in[v];
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n >> m >> q;
  for (int i=0; i<m; ++i) {
    cin >> a >> b;
    --a, --b;
    adj[b].push_back(a);
  }
  for (int i=0; i<n; ++i) {
    B[i] = visited[i] = ver[i] = -1;
    while (!pq.empty()) pq.pop();
    pq.push({-1, i, -1});
    for (int j=0; j<rt; ++j) {
      dp[i][j] = {(ll)-1e9, -1};
    }
    for (auto u : adj[i]) {
      pq.push({dp[u][0][0], u, 0});
    }
    for (int j=0; j<rt; ++j) {
      while (!pq.empty()) {
        auto [w, u, x] = pq.top();
        pq.pop();
        if (x != -1 && x != rt-1 && dp[u][x+1][1] != -1) {
          pq.push({dp[u][x+1][0], u, x+1});
        }
        if (x == -1) {
          dp[i][j] = {w+1, u};
          break;
        }
        else if (ver[dp[u][x][1]] != i) {
          dp[i][j] = {w+1, dp[u][x][1]};
          ver[dp[u][x][1]] = i;
          break;
        }
      }
    }
  }
  while (q--) {
    cin >> a >> k;
    --a;
    for (int i=0; i<k; ++i) {
      cin >> b;
      --b;
      B[b] = q;
    }
    if (k < rt) {
      for (int i=0; i<rt; ++i) {
        if (dp[a][i][1] == -1) {
          cout << "-1\n";
          break;
        }
        if (B[dp[a][i][1]] != q) {
          cout << dp[a][i][0] << '\n';
          break;
        }
      }
    }
    else {
      dfs(a);
      Q.push(a);
      f = -1;
      while (!Q.empty()) {
        auto u = Q.front();
        Q.pop();
        if (B[u] != q) f = max(f, dist[u]);
        for (auto v : adj[u]) {
          --in[v];
          dist[v] = max(dist[v], dist[u]+1);
          if (!in[v]) Q.push(v);
        }
      }
      cout << f << '\n';
    }
  }
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:45:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |         auto [w, u, x] = pq.top();
      |              ^

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