oj.uz

답안 #963460

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
963460 2024-04-15T04:10:48 Z kilkuwu 게임 (APIO22_game) C++17
60 / 100
 4000 ms 39176 KB 
#include "game.h"

#include <bits/stdc++.h>

int n, k;

constexpr int N = 3e5 + 5;

int can_reach[N]; // can_reach from k -> 0
int be_reached[N]; // be reached from 0 -> k

std::vector<int> adj[N];
std::vector<int> radj[N];

void add_edge(int u, int v) {
  adj[u].push_back(v);
  radj[v].push_back(u);
}

void init(int _n, int _k) {
  n = _n, k = _k;
  for (int i = 0; i < k; i++) {
    can_reach[i] = i; // it can reach i -> k - 1
    be_reached[i] = i + 1; // can be reach from 0 -> i
  }
  for (int i = k; i < n; i++) {
    can_reach[i] = k; // can't reach any
    be_reached[i] = 0; // can't be reached by any
  }

  for (int i = 0; i + 1 < k; i++) {
    add_edge(i, i + 1);
  }
}

void update_can_reach(int u, int val) {
  if (can_reach[u] <= val) { // reach from can_reach[u] -> k - 1 
    return; // we don't care
  }
  can_reach[u] = val;
  for (int v : radj[u]) {
    update_can_reach(v, val);
  }
}

void update_be_reached(int u, int val) {
  if (be_reached[u] >= val) { // can be reached from 0 -> be_reached - 1
    return;
  }

  be_reached[u] = val;
  for (int v : adj[u]) {
    update_be_reached(v, val);
  }
}

int add_teleporter(int u, int v) {
  if (can_reach[v] < be_reached[u]) {
    return 1; 
  }
  update_can_reach(u, can_reach[v]);
  update_be_reached(v, be_reached[u]);
  add_edge(u, v);
  return 0;
}

Subtask #1
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14936 KB Output is correct
2 Correct 3 ms 14936 KB Output is correct
3 Correct 3 ms 14936 KB Output is correct
4 Correct 3 ms 14936 KB Output is correct
5 Correct 3 ms 14936 KB Output is correct
6 Correct 3 ms 14936 KB Output is correct
7 Correct 4 ms 14936 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14936 KB Output is correct
2 Correct 3 ms 14936 KB Output is correct
3 Correct 3 ms 14936 KB Output is correct
4 Correct 3 ms 14936 KB Output is correct
5 Correct 3 ms 14936 KB Output is correct
6 Correct 3 ms 14936 KB Output is correct
7 Correct 4 ms 14936 KB Output is correct
8 Correct 3 ms 14936 KB Output is correct
9 Correct 3 ms 14936 KB Output is correct
10 Correct 3 ms 14936 KB Output is correct
11 Correct 3 ms 14936 KB Output is correct
12 Correct 3 ms 14968 KB Output is correct
13 Correct 3 ms 14936 KB Output is correct
14 Correct 3 ms 14936 KB Output is correct
15 Correct 5 ms 14936 KB Output is correct
16 Correct 3 ms 14936 KB Output is correct
17 Correct 3 ms 14936 KB Output is correct
18 Correct 3 ms 14936 KB Output is correct
19 Correct 3 ms 14968 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14936 KB Output is correct
2 Correct 3 ms 14936 KB Output is correct
3 Correct 3 ms 14936 KB Output is correct
4 Correct 3 ms 14936 KB Output is correct
5 Correct 3 ms 14936 KB Output is correct
6 Correct 3 ms 14936 KB Output is correct
7 Correct 4 ms 14936 KB Output is correct
8 Correct 3 ms 14936 KB Output is correct
9 Correct 3 ms 14936 KB Output is correct
10 Correct 3 ms 14936 KB Output is correct
11 Correct 3 ms 14936 KB Output is correct
12 Correct 3 ms 14968 KB Output is correct
13 Correct 3 ms 14936 KB Output is correct
14 Correct 3 ms 14936 KB Output is correct
15 Correct 5 ms 14936 KB Output is correct
16 Correct 3 ms 14936 KB Output is correct
17 Correct 3 ms 14936 KB Output is correct
18 Correct 3 ms 14936 KB Output is correct
19 Correct 3 ms 14968 KB Output is correct
20 Correct 3 ms 14936 KB Output is correct
21 Correct 4 ms 14936 KB Output is correct
22 Correct 4 ms 14936 KB Output is correct
23 Correct 4 ms 15192 KB Output is correct
24 Correct 7 ms 15192 KB Output is correct
25 Correct 5 ms 15192 KB Output is correct
26 Correct 5 ms 14948 KB Output is correct
27 Correct 4 ms 14936 KB Output is correct
28 Correct 4 ms 15028 KB Output is correct
29 Correct 5 ms 15192 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14936 KB Output is correct
2 Correct 3 ms 14936 KB Output is correct
3 Correct 3 ms 14936 KB Output is correct
4 Correct 3 ms 14936 KB Output is correct
5 Correct 3 ms 14936 KB Output is correct
6 Correct 3 ms 14936 KB Output is correct
7 Correct 4 ms 14936 KB Output is correct
8 Correct 3 ms 14936 KB Output is correct
9 Correct 3 ms 14936 KB Output is correct
10 Correct 3 ms 14936 KB Output is correct
11 Correct 3 ms 14936 KB Output is correct
12 Correct 3 ms 14968 KB Output is correct
13 Correct 3 ms 14936 KB Output is correct
14 Correct 3 ms 14936 KB Output is correct
15 Correct 5 ms 14936 KB Output is correct
16 Correct 3 ms 14936 KB Output is correct
17 Correct 3 ms 14936 KB Output is correct
18 Correct 3 ms 14936 KB Output is correct
19 Correct 3 ms 14968 KB Output is correct
20 Correct 3 ms 14936 KB Output is correct
21 Correct 4 ms 14936 KB Output is correct
22 Correct 4 ms 14936 KB Output is correct
23 Correct 4 ms 15192 KB Output is correct
24 Correct 7 ms 15192 KB Output is correct
25 Correct 5 ms 15192 KB Output is correct
26 Correct 5 ms 14948 KB Output is correct
27 Correct 4 ms 14936 KB Output is correct
28 Correct 4 ms 15028 KB Output is correct
29 Correct 5 ms 15192 KB Output is correct
30 Correct 16 ms 16472 KB Output is correct
31 Correct 7 ms 15960 KB Output is correct
32 Correct 19 ms 17300 KB Output is correct
33 Correct 17 ms 17240 KB Output is correct
34 Correct 859 ms 17688 KB Output is correct
35 Correct 308 ms 17836 KB Output is correct
36 Correct 34 ms 17176 KB Output is correct
37 Correct 26 ms 17240 KB Output is correct
38 Correct 25 ms 17224 KB Output is correct
39 Correct 26 ms 16792 KB Output is correct
40 Correct 711 ms 18052 KB Output is correct
41 Correct 146 ms 17628 KB Output is correct
42 Correct 96 ms 17460 KB Output is correct
43 Correct 29 ms 17288 KB Output is correct
44 Correct 614 ms 17880 KB Output is correct

Subtask #5
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 14936 KB Output is correct
2 Correct 3 ms 14936 KB Output is correct
3 Correct 3 ms 14936 KB Output is correct
4 Correct 3 ms 14936 KB Output is correct
5 Correct 3 ms 14936 KB Output is correct
6 Correct 3 ms 14936 KB Output is correct
7 Correct 4 ms 14936 KB Output is correct
8 Correct 3 ms 14936 KB Output is correct
9 Correct 3 ms 14936 KB Output is correct
10 Correct 3 ms 14936 KB Output is correct
11 Correct 3 ms 14936 KB Output is correct
12 Correct 3 ms 14968 KB Output is correct
13 Correct 3 ms 14936 KB Output is correct
14 Correct 3 ms 14936 KB Output is correct
15 Correct 5 ms 14936 KB Output is correct
16 Correct 3 ms 14936 KB Output is correct
17 Correct 3 ms 14936 KB Output is correct
18 Correct 3 ms 14936 KB Output is correct
19 Correct 3 ms 14968 KB Output is correct
20 Correct 3 ms 14936 KB Output is correct
21 Correct 4 ms 14936 KB Output is correct
22 Correct 4 ms 14936 KB Output is correct
23 Correct 4 ms 15192 KB Output is correct
24 Correct 7 ms 15192 KB Output is correct
25 Correct 5 ms 15192 KB Output is correct
26 Correct 5 ms 14948 KB Output is correct
27 Correct 4 ms 14936 KB Output is correct
28 Correct 4 ms 15028 KB Output is correct
29 Correct 5 ms 15192 KB Output is correct
30 Correct 16 ms 16472 KB Output is correct
31 Correct 7 ms 15960 KB Output is correct
32 Correct 19 ms 17300 KB Output is correct
33 Correct 17 ms 17240 KB Output is correct
34 Correct 859 ms 17688 KB Output is correct
35 Correct 308 ms 17836 KB Output is correct
36 Correct 34 ms 17176 KB Output is correct
37 Correct 26 ms 17240 KB Output is correct
38 Correct 25 ms 17224 KB Output is correct
39 Correct 26 ms 16792 KB Output is correct
40 Correct 711 ms 18052 KB Output is correct
41 Correct 146 ms 17628 KB Output is correct
42 Correct 96 ms 17460 KB Output is correct
43 Correct 29 ms 17288 KB Output is correct
44 Correct 614 ms 17880 KB Output is correct
45 Correct 184 ms 29092 KB Output is correct
46 Correct 7 ms 17240 KB Output is correct
47 Correct 7 ms 17496 KB Output is correct
48 Correct 266 ms 38664 KB Output is correct
49 Correct 202 ms 36124 KB Output is correct
50 Execution timed out 4070 ms 39176 KB Time limit exceeded
51 Halted 0 ms 0 KB -