oj.uz

Submission #839171

# Submission time Handle Problem Language Result Execution time Memory
839171 2023-08-28T23:56:49 Z asdfgrace Tropical Garden (IOI11_garden) C++17
69 / 100
 5000 ms 50368 KB 
#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
  const int LOG = 31;
  vector<vector<int>> edges(N);
  for (int i = 0; i < M; ++i) {
    edges[R[i][0]].push_back(R[i][1]);
    edges[R[i][1]].push_back(R[i][0]);
  }
  vector<int> next(2 * N, -1);
  for (int i = 0; i < N; ++i) {
    int x = edges[i][0];
    next[2 * i] = (i == edges[x][0] ? 2 * x + 1 : 2 * x);
    x = ((int) edges[i].size() == 1 ? edges[i][0] : edges[i][1]);
    next[2 * i + 1] = (i == edges[x][0] ? 2 * x + 1 : 2 * x);
  }
  vector<vector<int>> lift(LOG, vector<int>(2 * N));
  lift[0] = next;
  for (int j = 1; j < LOG; ++j) {
    for (int i = 0; i < 2 * N; ++i) {
      lift[j][i] = lift[j - 1][lift[j - 1][i]];
    }
  }
  auto get = [&](int i, int k) {
    for (int j = LOG - 1; j >= 0; --j) {
      if (k >= 1 << j) {
        i = lift[j][i];
        k -= 1 << j;
      }
    }
    return i;
  };
  for (int j = 0; j < Q; ++j) {
    int k = G[j], cnt = 0;
    for (int i = 0; i < N; ++i) {
      if (get(i * 2, k) / 2 == P) ++cnt;
    }
    answer(cnt);
  }
}

Subtask #1
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 516 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 2 ms 724 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 516 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 9 ms 7524 KB Output is correct
12 Correct 20 ms 13256 KB Output is correct
13 Correct 34 ms 28600 KB Output is correct
14 Correct 69 ms 45584 KB Output is correct
15 Correct 67 ms 46164 KB Output is correct
16 Correct 58 ms 32076 KB Output is correct
17 Correct 48 ms 27564 KB Output is correct
18 Correct 22 ms 13240 KB Output is correct
19 Correct 65 ms 45516 KB Output is correct
20 Correct 70 ms 46156 KB Output is correct
21 Correct 52 ms 31992 KB Output is correct
22 Correct 51 ms 27564 KB Output is correct
23 Correct 75 ms 50368 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 516 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 9 ms 7524 KB Output is correct
12 Correct 20 ms 13256 KB Output is correct
13 Correct 34 ms 28600 KB Output is correct
14 Correct 69 ms 45584 KB Output is correct
15 Correct 67 ms 46164 KB Output is correct
16 Correct 58 ms 32076 KB Output is correct
17 Correct 48 ms 27564 KB Output is correct
18 Correct 22 ms 13240 KB Output is correct
19 Correct 65 ms 45516 KB Output is correct
20 Correct 70 ms 46156 KB Output is correct
21 Correct 52 ms 31992 KB Output is correct
22 Correct 51 ms 27564 KB Output is correct
23 Correct 75 ms 50368 KB Output is correct
24 Correct 6 ms 340 KB Output is correct
25 Correct 2311 ms 7764 KB Output is correct
26 Correct 3882 ms 13268 KB Output is correct
27 Correct 4743 ms 28684 KB Output is correct
28 Execution timed out 5031 ms 45532 KB Time limit exceeded
29 Halted 0 ms 0 KB -