oj.uz

Submission #773519

# Submission time Handle Problem Language Result Execution time Memory
773519 2023-07-05T06:25:59 Z LittleCube Game (APIO22_game) C++17
60 / 100
 1796 ms 262144 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
{
  int n, k, from[300000][10], to[300000][10], where[300000][10];
  vector<int> Ef[300000][10], Et[300000][10];
  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 + 8) / 8;
      for (int j = 1; j <= 8; 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 << 3 | (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] = 9;
    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);
    from[v][l] = max(from[v][l], from[u][l]);
    to[u][l] = min(to[u][l], to[v][l]);
    vector<int> s;
    bool flag = 0;
    if (v >= k)
    {
      update_from(v, l, s);
      flag |= (from[v][l] > to[v][l]);
    }
    if (u >= k)
    {
      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 << 3 | (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] = 9;
    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;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 141104 KB Output is correct
2 Correct 91 ms 141088 KB Output is correct
3 Correct 99 ms 141100 KB Output is correct
4 Correct 81 ms 141084 KB Output is correct
5 Correct 88 ms 141168 KB Output is correct
6 Correct 67 ms 141156 KB Output is correct
7 Correct 75 ms 141120 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 141104 KB Output is correct
2 Correct 91 ms 141088 KB Output is correct
3 Correct 99 ms 141100 KB Output is correct
4 Correct 81 ms 141084 KB Output is correct
5 Correct 88 ms 141168 KB Output is correct
6 Correct 67 ms 141156 KB Output is correct
7 Correct 75 ms 141120 KB Output is correct
8 Correct 79 ms 141112 KB Output is correct
9 Correct 67 ms 141180 KB Output is correct
10 Correct 66 ms 141124 KB Output is correct
11 Correct 72 ms 141132 KB Output is correct
12 Correct 72 ms 141188 KB Output is correct
13 Correct 93 ms 141148 KB Output is correct
14 Correct 68 ms 141128 KB Output is correct
15 Correct 77 ms 141228 KB Output is correct
16 Correct 75 ms 141116 KB Output is correct
17 Correct 74 ms 141124 KB Output is correct
18 Correct 79 ms 141104 KB Output is correct
19 Correct 75 ms 141128 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 141104 KB Output is correct
2 Correct 91 ms 141088 KB Output is correct
3 Correct 99 ms 141100 KB Output is correct
4 Correct 81 ms 141084 KB Output is correct
5 Correct 88 ms 141168 KB Output is correct
6 Correct 67 ms 141156 KB Output is correct
7 Correct 75 ms 141120 KB Output is correct
8 Correct 79 ms 141112 KB Output is correct
9 Correct 67 ms 141180 KB Output is correct
10 Correct 66 ms 141124 KB Output is correct
11 Correct 72 ms 141132 KB Output is correct
12 Correct 72 ms 141188 KB Output is correct
13 Correct 93 ms 141148 KB Output is correct
14 Correct 68 ms 141128 KB Output is correct
15 Correct 77 ms 141228 KB Output is correct
16 Correct 75 ms 141116 KB Output is correct
17 Correct 74 ms 141124 KB Output is correct
18 Correct 79 ms 141104 KB Output is correct
19 Correct 75 ms 141128 KB Output is correct
20 Correct 74 ms 141328 KB Output is correct
21 Correct 73 ms 141328 KB Output is correct
22 Correct 72 ms 141384 KB Output is correct
23 Correct 79 ms 141332 KB Output is correct
24 Correct 81 ms 141480 KB Output is correct
25 Correct 89 ms 141476 KB Output is correct
26 Correct 79 ms 141400 KB Output is correct
27 Correct 76 ms 141432 KB Output is correct
28 Correct 85 ms 141420 KB Output is correct
29 Correct 84 ms 141356 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 141104 KB Output is correct
2 Correct 91 ms 141088 KB Output is correct
3 Correct 99 ms 141100 KB Output is correct
4 Correct 81 ms 141084 KB Output is correct
5 Correct 88 ms 141168 KB Output is correct
6 Correct 67 ms 141156 KB Output is correct
7 Correct 75 ms 141120 KB Output is correct
8 Correct 79 ms 141112 KB Output is correct
9 Correct 67 ms 141180 KB Output is correct
10 Correct 66 ms 141124 KB Output is correct
11 Correct 72 ms 141132 KB Output is correct
12 Correct 72 ms 141188 KB Output is correct
13 Correct 93 ms 141148 KB Output is correct
14 Correct 68 ms 141128 KB Output is correct
15 Correct 77 ms 141228 KB Output is correct
16 Correct 75 ms 141116 KB Output is correct
17 Correct 74 ms 141124 KB Output is correct
18 Correct 79 ms 141104 KB Output is correct
19 Correct 75 ms 141128 KB Output is correct
20 Correct 74 ms 141328 KB Output is correct
21 Correct 73 ms 141328 KB Output is correct
22 Correct 72 ms 141384 KB Output is correct
23 Correct 79 ms 141332 KB Output is correct
24 Correct 81 ms 141480 KB Output is correct
25 Correct 89 ms 141476 KB Output is correct
26 Correct 79 ms 141400 KB Output is correct
27 Correct 76 ms 141432 KB Output is correct
28 Correct 85 ms 141420 KB Output is correct
29 Correct 84 ms 141356 KB Output is correct
30 Correct 96 ms 145772 KB Output is correct
31 Correct 83 ms 145096 KB Output is correct
32 Correct 115 ms 147948 KB Output is correct
33 Correct 102 ms 146556 KB Output is correct
34 Correct 210 ms 156676 KB Output is correct
35 Correct 138 ms 150076 KB Output is correct
36 Correct 155 ms 148348 KB Output is correct
37 Correct 138 ms 150196 KB Output is correct
38 Correct 117 ms 147144 KB Output is correct
39 Correct 119 ms 148060 KB Output is correct
40 Correct 197 ms 155948 KB Output is correct
41 Correct 119 ms 148552 KB Output is correct
42 Correct 116 ms 147616 KB Output is correct
43 Correct 186 ms 153868 KB Output is correct
44 Correct 163 ms 152664 KB Output is correct

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 141104 KB Output is correct
2 Correct 91 ms 141088 KB Output is correct
3 Correct 99 ms 141100 KB Output is correct
4 Correct 81 ms 141084 KB Output is correct
5 Correct 88 ms 141168 KB Output is correct
6 Correct 67 ms 141156 KB Output is correct
7 Correct 75 ms 141120 KB Output is correct
8 Correct 79 ms 141112 KB Output is correct
9 Correct 67 ms 141180 KB Output is correct
10 Correct 66 ms 141124 KB Output is correct
11 Correct 72 ms 141132 KB Output is correct
12 Correct 72 ms 141188 KB Output is correct
13 Correct 93 ms 141148 KB Output is correct
14 Correct 68 ms 141128 KB Output is correct
15 Correct 77 ms 141228 KB Output is correct
16 Correct 75 ms 141116 KB Output is correct
17 Correct 74 ms 141124 KB Output is correct
18 Correct 79 ms 141104 KB Output is correct
19 Correct 75 ms 141128 KB Output is correct
20 Correct 74 ms 141328 KB Output is correct
21 Correct 73 ms 141328 KB Output is correct
22 Correct 72 ms 141384 KB Output is correct
23 Correct 79 ms 141332 KB Output is correct
24 Correct 81 ms 141480 KB Output is correct
25 Correct 89 ms 141476 KB Output is correct
26 Correct 79 ms 141400 KB Output is correct
27 Correct 76 ms 141432 KB Output is correct
28 Correct 85 ms 141420 KB Output is correct
29 Correct 84 ms 141356 KB Output is correct
30 Correct 96 ms 145772 KB Output is correct
31 Correct 83 ms 145096 KB Output is correct
32 Correct 115 ms 147948 KB Output is correct
33 Correct 102 ms 146556 KB Output is correct
34 Correct 210 ms 156676 KB Output is correct
35 Correct 138 ms 150076 KB Output is correct
36 Correct 155 ms 148348 KB Output is correct
37 Correct 138 ms 150196 KB Output is correct
38 Correct 117 ms 147144 KB Output is correct
39 Correct 119 ms 148060 KB Output is correct
40 Correct 197 ms 155948 KB Output is correct
41 Correct 119 ms 148552 KB Output is correct
42 Correct 116 ms 147616 KB Output is correct
43 Correct 186 ms 153868 KB Output is correct
44 Correct 163 ms 152664 KB Output is correct
45 Correct 409 ms 187776 KB Output is correct
46 Correct 93 ms 176784 KB Output is correct
47 Correct 92 ms 176696 KB Output is correct
48 Correct 626 ms 209336 KB Output is correct
49 Correct 483 ms 195248 KB Output is correct
50 Runtime error 1796 ms 262144 KB Execution killed with signal 9
51 Halted 0 ms 0 KB -