oj.uz

Submission #821566

# Submission time Handle Problem Language Result Execution time Memory
821566 2023-08-11T11:39:49 Z radaiosm7 Game (APIO22_game) C++17
30 / 100
 82 ms 4064 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[30005];
int visited[30005];
int ind[30005];
int i, n, k, s;
int seg[120020];

int Query(int from, int to, int start=0, int ende=1005, int indx=1) {
  if (from == start && to == ende) return seg[indx];
  int mid = (start+ende)/2;
  if (to <= mid) return Query(from, to, start, mid, 2*indx);
  if (from > mid) return Query(from, to, mid+1, ende, 2*indx+1);
  else return min(Query(from, mid, start, mid, 2*indx), Query(mid+1, to, mid+1, ende, 2*indx+1));
}

void Insert(int val, int start=0, int ende=1005, int indx=1) {
  if (start == ende) {
    seg[indx] = val;
    ind[val] = s;
    ++s;
    return;
  }

  int mid = (start+ende)/2;
  if (s <= mid) Insert(val, start, mid, 2*indx);
  else Insert(val, mid+1, ende, 2*indx+1);
  seg[indx] = min(seg[2*indx], seg[2*indx+1]);
}

void Erase(int start=0, int ende=1005, int indx=1) {
  if (start == ende) {
    ind[seg[indx]] = -2;
    seg[indx] = INT_MAX;
    --s;
    return;
  }

  int mid = (start+ende)/2;
  if (s-1 <= mid) Erase(start, mid, 2*indx);
  else Erase(mid+1, ende, 2*indx+1);
  seg[indx] = min(seg[2*indx], seg[2*indx+1]);
}

void build(int start=0, int ende=1005, int indx=1) {
  if (start == ende) {
    seg[indx] = INT_MAX;
    return;
  }

  int mid = (start+ende)/2;
  build(start, mid, 2*indx);
  build(mid+1, ende, 2*indx+1);
  seg[indx] = min(seg[2*indx], seg[2*indx+1]);
}

void init(int N, int K) {
  n = N;
  k = K;
  for (i=0; i < k-1; ++i) adj[i].push_back(i+1);
  build();
}

bool dfs(int x) {
  Insert(x);
  bool ok = false;

  for (auto y : adj[x]) {
    if (ind[y] == -2) continue;
    else if (ind[y] == -1) ok |= dfs(y);
    else if (Query(ind[y], ind[x]) < k) return true;
    if (ok) break;
  }

  Erase();
  return ok;
}

int add_teleporter(int u, int v) {
  fill(ind, ind+n, -1);
  if (u == v) return (u < k) ? 1 : 0;
  adj[u].push_back(v);
  s = 0;
  Insert(u);
  if (dfs(v)) return 1;
  else Erase();
  return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 976 KB Output is correct
2 Correct 1 ms 976 KB Output is correct
3 Correct 2 ms 976 KB Output is correct
4 Correct 1 ms 976 KB Output is correct
5 Correct 1 ms 976 KB Output is correct
6 Correct 1 ms 976 KB Output is correct
7 Correct 2 ms 976 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 976 KB Output is correct
2 Correct 1 ms 976 KB Output is correct
3 Correct 2 ms 976 KB Output is correct
4 Correct 1 ms 976 KB Output is correct
5 Correct 1 ms 976 KB Output is correct
6 Correct 1 ms 976 KB Output is correct
7 Correct 2 ms 976 KB Output is correct
8 Correct 1 ms 976 KB Output is correct
9 Correct 1 ms 976 KB Output is correct
10 Correct 1 ms 976 KB Output is correct
11 Correct 1 ms 976 KB Output is correct
12 Correct 1 ms 976 KB Output is correct
13 Correct 1 ms 976 KB Output is correct
14 Correct 1 ms 976 KB Output is correct
15 Correct 1 ms 976 KB Output is correct
16 Correct 1 ms 976 KB Output is correct
17 Correct 1 ms 976 KB Output is correct
18 Correct 1 ms 976 KB Output is correct
19 Correct 1 ms 1008 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 976 KB Output is correct
2 Correct 1 ms 976 KB Output is correct
3 Correct 2 ms 976 KB Output is correct
4 Correct 1 ms 976 KB Output is correct
5 Correct 1 ms 976 KB Output is correct
6 Correct 1 ms 976 KB Output is correct
7 Correct 2 ms 976 KB Output is correct
8 Correct 1 ms 976 KB Output is correct
9 Correct 1 ms 976 KB Output is correct
10 Correct 1 ms 976 KB Output is correct
11 Correct 1 ms 976 KB Output is correct
12 Correct 1 ms 976 KB Output is correct
13 Correct 1 ms 976 KB Output is correct
14 Correct 1 ms 976 KB Output is correct
15 Correct 1 ms 976 KB Output is correct
16 Correct 1 ms 976 KB Output is correct
17 Correct 1 ms 976 KB Output is correct
18 Correct 1 ms 976 KB Output is correct
19 Correct 1 ms 1008 KB Output is correct
20 Correct 2 ms 1104 KB Output is correct
21 Correct 1 ms 976 KB Output is correct
22 Correct 2 ms 996 KB Output is correct
23 Correct 2 ms 976 KB Output is correct
24 Correct 19 ms 976 KB Output is correct
25 Correct 82 ms 1076 KB Output is correct
26 Correct 49 ms 1048 KB Output is correct
27 Correct 7 ms 1064 KB Output is correct
28 Correct 41 ms 1068 KB Output is correct
29 Correct 80 ms 1060 KB Output is correct

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 976 KB Output is correct
2 Correct 1 ms 976 KB Output is correct
3 Correct 2 ms 976 KB Output is correct
4 Correct 1 ms 976 KB Output is correct
5 Correct 1 ms 976 KB Output is correct
6 Correct 1 ms 976 KB Output is correct
7 Correct 2 ms 976 KB Output is correct
8 Correct 1 ms 976 KB Output is correct
9 Correct 1 ms 976 KB Output is correct
10 Correct 1 ms 976 KB Output is correct
11 Correct 1 ms 976 KB Output is correct
12 Correct 1 ms 976 KB Output is correct
13 Correct 1 ms 976 KB Output is correct
14 Correct 1 ms 976 KB Output is correct
15 Correct 1 ms 976 KB Output is correct
16 Correct 1 ms 976 KB Output is correct
17 Correct 1 ms 976 KB Output is correct
18 Correct 1 ms 976 KB Output is correct
19 Correct 1 ms 1008 KB Output is correct
20 Correct 2 ms 1104 KB Output is correct
21 Correct 1 ms 976 KB Output is correct
22 Correct 2 ms 996 KB Output is correct
23 Correct 2 ms 976 KB Output is correct
24 Correct 19 ms 976 KB Output is correct
25 Correct 82 ms 1076 KB Output is correct
26 Correct 49 ms 1048 KB Output is correct
27 Correct 7 ms 1064 KB Output is correct
28 Correct 41 ms 1068 KB Output is correct
29 Correct 80 ms 1060 KB Output is correct
30 Correct 66 ms 1664 KB Output is correct
31 Correct 30 ms 1376 KB Output is correct
32 Runtime error 66 ms 4064 KB Execution killed with signal 11
33 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 976 KB Output is correct
2 Correct 1 ms 976 KB Output is correct
3 Correct 2 ms 976 KB Output is correct
4 Correct 1 ms 976 KB Output is correct
5 Correct 1 ms 976 KB Output is correct
6 Correct 1 ms 976 KB Output is correct
7 Correct 2 ms 976 KB Output is correct
8 Correct 1 ms 976 KB Output is correct
9 Correct 1 ms 976 KB Output is correct
10 Correct 1 ms 976 KB Output is correct
11 Correct 1 ms 976 KB Output is correct
12 Correct 1 ms 976 KB Output is correct
13 Correct 1 ms 976 KB Output is correct
14 Correct 1 ms 976 KB Output is correct
15 Correct 1 ms 976 KB Output is correct
16 Correct 1 ms 976 KB Output is correct
17 Correct 1 ms 976 KB Output is correct
18 Correct 1 ms 976 KB Output is correct
19 Correct 1 ms 1008 KB Output is correct
20 Correct 2 ms 1104 KB Output is correct
21 Correct 1 ms 976 KB Output is correct
22 Correct 2 ms 996 KB Output is correct
23 Correct 2 ms 976 KB Output is correct
24 Correct 19 ms 976 KB Output is correct
25 Correct 82 ms 1076 KB Output is correct
26 Correct 49 ms 1048 KB Output is correct
27 Correct 7 ms 1064 KB Output is correct
28 Correct 41 ms 1068 KB Output is correct
29 Correct 80 ms 1060 KB Output is correct
30 Correct 66 ms 1664 KB Output is correct
31 Correct 30 ms 1376 KB Output is correct
32 Runtime error 66 ms 4064 KB Execution killed with signal 11
33 Halted 0 ms 0 KB -