oj.uz

Submission #964598

# Submission time Handle Problem Language Result Execution time Memory
964598 2024-04-17T07:36:34 Z abczz Bitaro’s Party (JOI18_bitaro) C++14
7 / 100
 2000 ms 18304 KB 
#include <iostream>
#include <vector>
#include <array>
#include <queue>
#define ll long long

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 = 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.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)-1e18, -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);
      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: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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8024 KB Output is correct
2 Correct 2 ms 8120 KB Output is correct
3 Correct 3 ms 8028 KB Output is correct
4 Correct 2 ms 8024 KB Output is correct
5 Correct 6 ms 14340 KB Output is correct
6 Correct 5 ms 14172 KB Output is correct
7 Correct 6 ms 14172 KB Output is correct
8 Correct 14 ms 14344 KB Output is correct
9 Correct 14 ms 14340 KB Output is correct
10 Correct 15 ms 14268 KB Output is correct
11 Correct 14 ms 14168 KB Output is correct
12 Correct 9 ms 14272 KB Output is correct
13 Correct 14 ms 14172 KB Output is correct
14 Correct 13 ms 14172 KB Output is correct
15 Correct 7 ms 14168 KB Output is correct
16 Correct 11 ms 14280 KB Output is correct
17 Correct 11 ms 14172 KB Output is correct
18 Correct 8 ms 14172 KB Output is correct
19 Correct 13 ms 14172 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8024 KB Output is correct
2 Correct 2 ms 8120 KB Output is correct
3 Correct 3 ms 8028 KB Output is correct
4 Correct 2 ms 8024 KB Output is correct
5 Correct 6 ms 14340 KB Output is correct
6 Correct 5 ms 14172 KB Output is correct
7 Correct 6 ms 14172 KB Output is correct
8 Correct 14 ms 14344 KB Output is correct
9 Correct 14 ms 14340 KB Output is correct
10 Correct 15 ms 14268 KB Output is correct
11 Correct 14 ms 14168 KB Output is correct
12 Correct 9 ms 14272 KB Output is correct
13 Correct 14 ms 14172 KB Output is correct
14 Correct 13 ms 14172 KB Output is correct
15 Correct 7 ms 14168 KB Output is correct
16 Correct 11 ms 14280 KB Output is correct
17 Correct 11 ms 14172 KB Output is correct
18 Correct 8 ms 14172 KB Output is correct
19 Correct 13 ms 14172 KB Output is correct
20 Correct 1944 ms 18264 KB Output is correct
21 Correct 1527 ms 18260 KB Output is correct
22 Execution timed out 2033 ms 18304 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 86.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8024 KB Output is correct
2 Correct 2 ms 8120 KB Output is correct
3 Correct 3 ms 8028 KB Output is correct
4 Correct 2 ms 8024 KB Output is correct
5 Correct 6 ms 14340 KB Output is correct
6 Correct 5 ms 14172 KB Output is correct
7 Correct 6 ms 14172 KB Output is correct
8 Correct 14 ms 14344 KB Output is correct
9 Correct 14 ms 14340 KB Output is correct
10 Correct 15 ms 14268 KB Output is correct
11 Correct 14 ms 14168 KB Output is correct
12 Correct 9 ms 14272 KB Output is correct
13 Correct 14 ms 14172 KB Output is correct
14 Correct 13 ms 14172 KB Output is correct
15 Correct 7 ms 14168 KB Output is correct
16 Correct 11 ms 14280 KB Output is correct
17 Correct 11 ms 14172 KB Output is correct
18 Correct 8 ms 14172 KB Output is correct
19 Correct 13 ms 14172 KB Output is correct
20 Correct 1944 ms 18264 KB Output is correct
21 Correct 1527 ms 18260 KB Output is correct
22 Execution timed out 2033 ms 18304 KB Time limit exceeded
23 Halted 0 ms 0 KB -