oj.uz

답안 #964604

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
964604 2024-04-17T07:43:59 Z abczz Bitaro’s Party (JOI18_bitaro) C++14
14 / 100
 989 ms 272544 KB 
#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;
  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);
      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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6232 KB Output is correct
2 Correct 2 ms 6236 KB Output is correct
3 Correct 2 ms 6404 KB Output is correct
4 Correct 2 ms 6236 KB Output is correct
5 Correct 4 ms 10560 KB Output is correct
6 Correct 6 ms 10328 KB Output is correct
7 Correct 6 ms 10340 KB Output is correct
8 Correct 7 ms 10332 KB Output is correct
9 Correct 7 ms 10588 KB Output is correct
10 Correct 7 ms 10560 KB Output is correct
11 Correct 8 ms 10332 KB Output is correct
12 Correct 7 ms 10332 KB Output is correct
13 Correct 8 ms 10332 KB Output is correct
14 Correct 6 ms 10512 KB Output is correct
15 Correct 7 ms 10332 KB Output is correct
16 Correct 6 ms 10332 KB Output is correct
17 Correct 6 ms 10332 KB Output is correct
18 Correct 5 ms 10512 KB Output is correct
19 Correct 7 ms 10332 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6232 KB Output is correct
2 Correct 2 ms 6236 KB Output is correct
3 Correct 2 ms 6404 KB Output is correct
4 Correct 2 ms 6236 KB Output is correct
5 Correct 4 ms 10560 KB Output is correct
6 Correct 6 ms 10328 KB Output is correct
7 Correct 6 ms 10340 KB Output is correct
8 Correct 7 ms 10332 KB Output is correct
9 Correct 7 ms 10588 KB Output is correct
10 Correct 7 ms 10560 KB Output is correct
11 Correct 8 ms 10332 KB Output is correct
12 Correct 7 ms 10332 KB Output is correct
13 Correct 8 ms 10332 KB Output is correct
14 Correct 6 ms 10512 KB Output is correct
15 Correct 7 ms 10332 KB Output is correct
16 Correct 6 ms 10332 KB Output is correct
17 Correct 6 ms 10332 KB Output is correct
18 Correct 5 ms 10512 KB Output is correct
19 Correct 7 ms 10332 KB Output is correct
20 Correct 965 ms 13276 KB Output is correct
21 Correct 657 ms 13280 KB Output is correct
22 Correct 989 ms 13296 KB Output is correct
23 Correct 479 ms 13300 KB Output is correct
24 Correct 641 ms 268148 KB Output is correct
25 Correct 675 ms 268272 KB Output is correct
26 Correct 666 ms 268376 KB Output is correct
27 Correct 664 ms 271224 KB Output is correct
28 Correct 579 ms 271536 KB Output is correct
29 Correct 596 ms 272544 KB Output is correct
30 Correct 581 ms 268824 KB Output is correct
31 Correct 612 ms 268972 KB Output is correct
32 Correct 593 ms 269016 KB Output is correct
33 Correct 461 ms 268408 KB Output is correct
34 Correct 439 ms 268208 KB Output is correct
35 Correct 456 ms 268320 KB Output is correct
36 Correct 510 ms 268368 KB Output is correct
37 Correct 512 ms 268216 KB Output is correct
38 Correct 533 ms 268288 KB Output is correct

Subtask #3
0 / 86.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6232 KB Output is correct
2 Correct 2 ms 6236 KB Output is correct
3 Correct 2 ms 6404 KB Output is correct
4 Correct 2 ms 6236 KB Output is correct
5 Correct 4 ms 10560 KB Output is correct
6 Correct 6 ms 10328 KB Output is correct
7 Correct 6 ms 10340 KB Output is correct
8 Correct 7 ms 10332 KB Output is correct
9 Correct 7 ms 10588 KB Output is correct
10 Correct 7 ms 10560 KB Output is correct
11 Correct 8 ms 10332 KB Output is correct
12 Correct 7 ms 10332 KB Output is correct
13 Correct 8 ms 10332 KB Output is correct
14 Correct 6 ms 10512 KB Output is correct
15 Correct 7 ms 10332 KB Output is correct
16 Correct 6 ms 10332 KB Output is correct
17 Correct 6 ms 10332 KB Output is correct
18 Correct 5 ms 10512 KB Output is correct
19 Correct 7 ms 10332 KB Output is correct
20 Correct 965 ms 13276 KB Output is correct
21 Correct 657 ms 13280 KB Output is correct
22 Correct 989 ms 13296 KB Output is correct
23 Correct 479 ms 13300 KB Output is correct
24 Correct 641 ms 268148 KB Output is correct
25 Correct 675 ms 268272 KB Output is correct
26 Correct 666 ms 268376 KB Output is correct
27 Correct 664 ms 271224 KB Output is correct
28 Correct 579 ms 271536 KB Output is correct
29 Correct 596 ms 272544 KB Output is correct
30 Correct 581 ms 268824 KB Output is correct
31 Correct 612 ms 268972 KB Output is correct
32 Correct 593 ms 269016 KB Output is correct
33 Correct 461 ms 268408 KB Output is correct
34 Correct 439 ms 268208 KB Output is correct
35 Correct 456 ms 268320 KB Output is correct
36 Correct 510 ms 268368 KB Output is correct
37 Correct 512 ms 268216 KB Output is correct
38 Correct 533 ms 268288 KB Output is correct
39 Correct 653 ms 269552 KB Output is correct
40 Correct 633 ms 268764 KB Output is correct
41 Correct 647 ms 268684 KB Output is correct
42 Incorrect 698 ms 268680 KB Output isn't correct
43 Halted 0 ms 0 KB -