oj.uz

Submission #964581

# Submission time Handle Problem Language Result Execution time Memory
964581 2024-04-17T06:56:20 Z abczz Bitaro’s Party (JOI18_bitaro) C++14
0 / 100
 3 ms 8028 KB 
#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 (B[dp[a][i][1]] != q) {
          cout << max((ll)-1, 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

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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8028 KB Output is correct
2 Incorrect 2 ms 8028 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8028 KB Output is correct
2 Incorrect 2 ms 8028 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8028 KB Output is correct
2 Incorrect 2 ms 8028 KB Output isn't correct
3 Halted 0 ms 0 KB -