oj.uz

Submission #774274

# Submission time Handle Problem Language Result Execution time Memory
774274 2023-07-05T13:34:40 Z LittleCube Game (APIO22_game) C++17
60 / 100
 4000 ms 121400 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#include "game.h"
#ifndef EVAL
#include "game_grader.cpp"
#endif
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;

namespace
{
  const int P = 100;
  int n, k, from[300000][5], to[300000][5], where[300000][5];
  vector<int> Ef[300000][5], Et[300000][5];
  void update_from(int u, int layer, vector<int> &same)
  {
    if (from[u][layer] == to[u][layer])
      same.emplace_back(u);
    for (auto v : Ef[u][layer])
      if (from[u][layer] > from[v][layer])
      {
        from[v][layer] = from[u][layer];
        update_from(v, layer, same);
      }
  }
  void update_to(int u, int layer, vector<int> &same)
  {
    if (from[u][layer] == to[u][layer])
      same.emplace_back(u);
    for (auto v : Et[u][layer])
      if (to[u][layer] < to[v][layer])
      {
        to[v][layer] = to[u][layer];
        update_to(v, layer, same);
      }
  }

  void build(int i = 1, int L = 0, int R = k - 1, int l = 0)
  {
    for (int j = L; j <= R; j++)
      where[j][l] = i;
    if (L != R)
    {
      int range = (R - L + P) / P;
      for (int j = 1; j <= P; j++)
      {
        int ml = L + range * (j - 1), mr = min(R, L + range * j - 1);
        for (int p = ml; p <= mr; p++)
          from[p][l] = to[p][l] = j;
        if (ml <= mr)
          build(i * P + (j - 1), ml, mr, l + 1);
      }
    }
    else
      from[L][l] = 2, to[L][l] = 1;
  }

  int add_edge(int, int, int, int);

  int add_node(int u, int i, int l)
  {
    if (where[u][l])
      return 0;
    where[u][l] = i;
    from[u][l] = 0, to[u][l] = P + 1;
    bool flag = 0;
    for (auto v : Et[u][l - 1])
      if (where[u][l] == where[v][l])
        flag |= add_edge(v, u, i, l);
    for (auto v : Ef[u][l - 1])
      if (where[u][l] == where[v][l])
        flag |= add_edge(u, v, i, l);

    return flag | (from[u][l] > to[u][l]);
  }

  int add_edge(int u, int v, int i = 1, int l = 0)
  {
    Ef[u][l].emplace_back(v);
    Et[v][l].emplace_back(u);
    vector<int> s;
    bool flag = 0;
    if (v >= k && from[v][l] < from[u][l])
    {
      from[v][l] = from[u][l];
      update_from(v, l, s);
      flag |= (from[v][l] > to[v][l]);
    }
    if (u >= k && to[u][l] > to[v][l])
    {
      to[u][l] = to[v][l];
      update_to(u, l, s);
      flag |= (from[u][l] > to[u][l]);
    }
    if (where[u][l + 1] == where[v][l + 1] && where[u][l + 1] > 0)
      flag |= add_edge(u, v, where[u][l + 1], l + 1);
    for (int w : s)
      flag |= add_node(w, i * P + (from[w][l] - 1), l + 1);
    return flag;
  }
}

void init(int n, int k)
{
  ::n = n, ::k = k;
  build();
  for (int i = k; i < n; i++)
  {
    from[i][0] = 0, to[i][0] = P + 1;
    where[i][0] = 1;
  }
}

int add_teleporter(int u, int v)
{
  if (u < k && v < k)
  {
    if (v <= u)
      return 1;
    return 0;
  }
  bool ans = add_edge(u, v);
  // cout << u << ' ' << v << '\n';
  // for (int p = 0; p < 5; p++)
  //   for (int i = 0; i < n; i++)
  //     cout << from[i][p] << ' ' << to[i][p] << ' ' << " \n"[i == n - 1];

  // for (int p = 0; p < 5; p++)
  //   for (int i = 0; i < n; i++)
  //     cout << where[i][p] << " \n"[i == n - 1];
  // cout << '\n';
  return ans;
}

Compilation message

game.cpp: In function 'void init(int, int)':
game.cpp:43:17: warning: array subscript 5 is above array bounds of 'int [5]' [-Warray-bounds]
   43 |       where[j][l] = i;
      |       ~~~~~~~~~~^
game.cpp:57:16: warning: array subscript 5 is above array bounds of 'int [5]' [-Warray-bounds]
   57 |       from[L][l] = 2, to[L][l] = 1;
      |       ~~~~~~~~~^
game.cpp:57:30: warning: array subscript 5 is above array bounds of 'int [5]' [-Warray-bounds]
   57 |       from[L][l] = 2, to[L][l] = 1;
      |                       ~~~~~~~^
game.cpp:51:31: warning: array subscript 5 is above array bounds of 'int [5]' [-Warray-bounds]
   51 |           from[p][l] = to[p][l] = j;
      |                        ~~~~~~~^
game.cpp:51:20: warning: array subscript 5 is above array bounds of 'int [5]' [-Warray-bounds]
   51 |           from[p][l] = to[p][l] = j;
      |           ~~~~~~~~~^
game.cpp:43:17: warning: array subscript 6 is above array bounds of 'int [5]' [-Warray-bounds]
   43 |       where[j][l] = i;
      |       ~~~~~~~~~~^
game.cpp:57:16: warning: array subscript 6 is above array bounds of 'int [5]' [-Warray-bounds]
   57 |       from[L][l] = 2, to[L][l] = 1;
      |       ~~~~~~~~~^
game.cpp:57:30: warning: array subscript 6 is above array bounds of 'int [5]' [-Warray-bounds]
   57 |       from[L][l] = 2, to[L][l] = 1;
      |                       ~~~~~~~^
game.cpp:51:31: warning: array subscript 6 is above array bounds of 'int [5]' [-Warray-bounds]
   51 |           from[p][l] = to[p][l] = j;
      |                        ~~~~~~~^
game.cpp:51:20: warning: array subscript 6 is above array bounds of 'int [5]' [-Warray-bounds]
   51 |           from[p][l] = to[p][l] = j;
      |           ~~~~~~~~~^
game.cpp:43:17: warning: array subscript 7 is above array bounds of 'int [5]' [-Warray-bounds]
   43 |       where[j][l] = i;
      |       ~~~~~~~~~~^
game.cpp:57:16: warning: array subscript 7 is above array bounds of 'int [5]' [-Warray-bounds]
   57 |       from[L][l] = 2, to[L][l] = 1;
      |       ~~~~~~~~~^
game.cpp:57:30: warning: array subscript 7 is above array bounds of 'int [5]' [-Warray-bounds]
   57 |       from[L][l] = 2, to[L][l] = 1;
      |                       ~~~~~~~^
game.cpp:51:31: warning: array subscript 7 is above array bounds of 'int [5]' [-Warray-bounds]
   51 |           from[p][l] = to[p][l] = j;
      |                        ~~~~~~~^
game.cpp:51:20: warning: array subscript 7 is above array bounds of 'int [5]' [-Warray-bounds]
   51 |           from[p][l] = to[p][l] = j;
      |           ~~~~~~~~~^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 70664 KB Output is correct
2 Correct 36 ms 70728 KB Output is correct
3 Correct 37 ms 70760 KB Output is correct
4 Correct 36 ms 70724 KB Output is correct
5 Correct 37 ms 70644 KB Output is correct
6 Correct 36 ms 70768 KB Output is correct
7 Correct 36 ms 70736 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 70664 KB Output is correct
2 Correct 36 ms 70728 KB Output is correct
3 Correct 37 ms 70760 KB Output is correct
4 Correct 36 ms 70724 KB Output is correct
5 Correct 37 ms 70644 KB Output is correct
6 Correct 36 ms 70768 KB Output is correct
7 Correct 36 ms 70736 KB Output is correct
8 Correct 36 ms 70676 KB Output is correct
9 Correct 36 ms 70700 KB Output is correct
10 Correct 36 ms 70804 KB Output is correct
11 Correct 36 ms 70704 KB Output is correct
12 Correct 37 ms 70728 KB Output is correct
13 Correct 36 ms 70700 KB Output is correct
14 Correct 37 ms 70736 KB Output is correct
15 Correct 37 ms 70680 KB Output is correct
16 Correct 38 ms 70736 KB Output is correct
17 Correct 38 ms 70736 KB Output is correct
18 Correct 37 ms 70700 KB Output is correct
19 Correct 36 ms 70644 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 70664 KB Output is correct
2 Correct 36 ms 70728 KB Output is correct
3 Correct 37 ms 70760 KB Output is correct
4 Correct 36 ms 70724 KB Output is correct
5 Correct 37 ms 70644 KB Output is correct
6 Correct 36 ms 70768 KB Output is correct
7 Correct 36 ms 70736 KB Output is correct
8 Correct 36 ms 70676 KB Output is correct
9 Correct 36 ms 70700 KB Output is correct
10 Correct 36 ms 70804 KB Output is correct
11 Correct 36 ms 70704 KB Output is correct
12 Correct 37 ms 70728 KB Output is correct
13 Correct 36 ms 70700 KB Output is correct
14 Correct 37 ms 70736 KB Output is correct
15 Correct 37 ms 70680 KB Output is correct
16 Correct 38 ms 70736 KB Output is correct
17 Correct 38 ms 70736 KB Output is correct
18 Correct 37 ms 70700 KB Output is correct
19 Correct 36 ms 70644 KB Output is correct
20 Correct 36 ms 70736 KB Output is correct
21 Correct 37 ms 70828 KB Output is correct
22 Correct 37 ms 70824 KB Output is correct
23 Correct 41 ms 70868 KB Output is correct
24 Correct 39 ms 70964 KB Output is correct
25 Correct 40 ms 70936 KB Output is correct
26 Correct 38 ms 70816 KB Output is correct
27 Correct 39 ms 70848 KB Output is correct
28 Correct 38 ms 70936 KB Output is correct
29 Correct 38 ms 70856 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 70664 KB Output is correct
2 Correct 36 ms 70728 KB Output is correct
3 Correct 37 ms 70760 KB Output is correct
4 Correct 36 ms 70724 KB Output is correct
5 Correct 37 ms 70644 KB Output is correct
6 Correct 36 ms 70768 KB Output is correct
7 Correct 36 ms 70736 KB Output is correct
8 Correct 36 ms 70676 KB Output is correct
9 Correct 36 ms 70700 KB Output is correct
10 Correct 36 ms 70804 KB Output is correct
11 Correct 36 ms 70704 KB Output is correct
12 Correct 37 ms 70728 KB Output is correct
13 Correct 36 ms 70700 KB Output is correct
14 Correct 37 ms 70736 KB Output is correct
15 Correct 37 ms 70680 KB Output is correct
16 Correct 38 ms 70736 KB Output is correct
17 Correct 38 ms 70736 KB Output is correct
18 Correct 37 ms 70700 KB Output is correct
19 Correct 36 ms 70644 KB Output is correct
20 Correct 36 ms 70736 KB Output is correct
21 Correct 37 ms 70828 KB Output is correct
22 Correct 37 ms 70824 KB Output is correct
23 Correct 41 ms 70868 KB Output is correct
24 Correct 39 ms 70964 KB Output is correct
25 Correct 40 ms 70936 KB Output is correct
26 Correct 38 ms 70816 KB Output is correct
27 Correct 39 ms 70848 KB Output is correct
28 Correct 38 ms 70936 KB Output is correct
29 Correct 38 ms 70856 KB Output is correct
30 Correct 55 ms 73632 KB Output is correct
31 Correct 53 ms 72876 KB Output is correct
32 Correct 68 ms 75836 KB Output is correct
33 Correct 59 ms 74312 KB Output is correct
34 Correct 260 ms 80824 KB Output is correct
35 Correct 113 ms 76600 KB Output is correct
36 Correct 72 ms 74392 KB Output is correct
37 Correct 87 ms 76144 KB Output is correct
38 Correct 65 ms 74216 KB Output is correct
39 Correct 69 ms 74440 KB Output is correct
40 Correct 217 ms 80416 KB Output is correct
41 Correct 100 ms 75376 KB Output is correct
42 Correct 84 ms 74964 KB Output is correct
43 Correct 118 ms 78948 KB Output is correct
44 Correct 277 ms 78364 KB Output is correct

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 70664 KB Output is correct
2 Correct 36 ms 70728 KB Output is correct
3 Correct 37 ms 70760 KB Output is correct
4 Correct 36 ms 70724 KB Output is correct
5 Correct 37 ms 70644 KB Output is correct
6 Correct 36 ms 70768 KB Output is correct
7 Correct 36 ms 70736 KB Output is correct
8 Correct 36 ms 70676 KB Output is correct
9 Correct 36 ms 70700 KB Output is correct
10 Correct 36 ms 70804 KB Output is correct
11 Correct 36 ms 70704 KB Output is correct
12 Correct 37 ms 70728 KB Output is correct
13 Correct 36 ms 70700 KB Output is correct
14 Correct 37 ms 70736 KB Output is correct
15 Correct 37 ms 70680 KB Output is correct
16 Correct 38 ms 70736 KB Output is correct
17 Correct 38 ms 70736 KB Output is correct
18 Correct 37 ms 70700 KB Output is correct
19 Correct 36 ms 70644 KB Output is correct
20 Correct 36 ms 70736 KB Output is correct
21 Correct 37 ms 70828 KB Output is correct
22 Correct 37 ms 70824 KB Output is correct
23 Correct 41 ms 70868 KB Output is correct
24 Correct 39 ms 70964 KB Output is correct
25 Correct 40 ms 70936 KB Output is correct
26 Correct 38 ms 70816 KB Output is correct
27 Correct 39 ms 70848 KB Output is correct
28 Correct 38 ms 70936 KB Output is correct
29 Correct 38 ms 70856 KB Output is correct
30 Correct 55 ms 73632 KB Output is correct
31 Correct 53 ms 72876 KB Output is correct
32 Correct 68 ms 75836 KB Output is correct
33 Correct 59 ms 74312 KB Output is correct
34 Correct 260 ms 80824 KB Output is correct
35 Correct 113 ms 76600 KB Output is correct
36 Correct 72 ms 74392 KB Output is correct
37 Correct 87 ms 76144 KB Output is correct
38 Correct 65 ms 74216 KB Output is correct
39 Correct 69 ms 74440 KB Output is correct
40 Correct 217 ms 80416 KB Output is correct
41 Correct 100 ms 75376 KB Output is correct
42 Correct 84 ms 74964 KB Output is correct
43 Correct 118 ms 78948 KB Output is correct
44 Correct 277 ms 78364 KB Output is correct
45 Correct 330 ms 99616 KB Output is correct
46 Correct 48 ms 88744 KB Output is correct
47 Correct 50 ms 88596 KB Output is correct
48 Correct 452 ms 121400 KB Output is correct
49 Correct 340 ms 107132 KB Output is correct
50 Execution timed out 4025 ms 116652 KB Time limit exceeded
51 Halted 0 ms 0 KB -