Submission #964593

#	Time	Username	Problem	Language	Result	Execution time	Memory
964593		abczz	Bitaro’s Party (JOI18_bitaro)	C++14	7 / 100	2037 ms	17284 KiB

bitaro

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

using namespace std;

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

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

int main() {
  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});
    for (int j=0; j<rt; ++j) {
      dp[i][j] = {(ll)-1e18, -1};
    }
    for (auto u : adj[i]) {
      for (int j=0; j<rt; ++j) {
        if (dp[u][j][1] == -1) break;
        pq.push(dp[u][j]);
      }
    }
    for (int j=0; j<rt; ++j) {
      while (!pq.empty()) {
        auto [w, u] = pq.top();
        pq.pop();
        if (ver[u] != i) {
          dp[i][j] = {w+1, u};
          ver[u] = 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);
      dist[a] = 0;
      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:46:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |         auto [w, u] = pq.top();
      |              ^

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