oj.uz

Submission #773484

# Submission time Handle Problem Language Result Execution time Memory
773484 2023-07-05T05:57:01 Z LittleCube Game (APIO22_game) C++17
2 / 100
 80 ms 141208 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 mid = (L + R) / 2;
      for (int j = L; j <= mid; j++)
        from[j][l] = to[j][l] = 1;
      for (int j = mid + 1; j <= R; j++)
        from[j][l] = to[j][l] = 2;
      build(i << 1, L, mid, l + 1);
      build(i << 1 | 1, mid + 1, R, 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] = 3;
    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]);
    }
    for (int w : s)
      if (from[w][l] == 1)
        flag |= add_node(w, i << 1, l + 1);
      else
        flag |= add_node(w, i << 1 | 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] = 3;
    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);
  // 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];
  // cout << '\n';
  // for (int p = 0; p < 5; p++)
  //   for (int i = 0; i < n; i++)
  //     cout << where[i][p] << " \n"[i == n - 1];
  // ;
  return ans;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 141096 KB Output is correct
2 Correct 66 ms 141204 KB Output is correct
3 Correct 66 ms 141144 KB Output is correct
4 Correct 78 ms 141152 KB Output is correct
5 Correct 68 ms 141096 KB Output is correct
6 Correct 73 ms 141124 KB Output is correct
7 Correct 69 ms 141128 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 141096 KB Output is correct
2 Correct 66 ms 141204 KB Output is correct
3 Correct 66 ms 141144 KB Output is correct
4 Correct 78 ms 141152 KB Output is correct
5 Correct 68 ms 141096 KB Output is correct
6 Correct 73 ms 141124 KB Output is correct
7 Correct 69 ms 141128 KB Output is correct
8 Correct 67 ms 141100 KB Output is correct
9 Correct 76 ms 141156 KB Output is correct
10 Correct 80 ms 141100 KB Output is correct
11 Correct 74 ms 141196 KB Output is correct
12 Correct 69 ms 141204 KB Output is correct
13 Correct 68 ms 141124 KB Output is correct
14 Incorrect 65 ms 141208 KB Wrong Answer[1]
15 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 141096 KB Output is correct
2 Correct 66 ms 141204 KB Output is correct
3 Correct 66 ms 141144 KB Output is correct
4 Correct 78 ms 141152 KB Output is correct
5 Correct 68 ms 141096 KB Output is correct
6 Correct 73 ms 141124 KB Output is correct
7 Correct 69 ms 141128 KB Output is correct
8 Correct 67 ms 141100 KB Output is correct
9 Correct 76 ms 141156 KB Output is correct
10 Correct 80 ms 141100 KB Output is correct
11 Correct 74 ms 141196 KB Output is correct
12 Correct 69 ms 141204 KB Output is correct
13 Correct 68 ms 141124 KB Output is correct
14 Incorrect 65 ms 141208 KB Wrong Answer[1]
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 141096 KB Output is correct
2 Correct 66 ms 141204 KB Output is correct
3 Correct 66 ms 141144 KB Output is correct
4 Correct 78 ms 141152 KB Output is correct
5 Correct 68 ms 141096 KB Output is correct
6 Correct 73 ms 141124 KB Output is correct
7 Correct 69 ms 141128 KB Output is correct
8 Correct 67 ms 141100 KB Output is correct
9 Correct 76 ms 141156 KB Output is correct
10 Correct 80 ms 141100 KB Output is correct
11 Correct 74 ms 141196 KB Output is correct
12 Correct 69 ms 141204 KB Output is correct
13 Correct 68 ms 141124 KB Output is correct
14 Incorrect 65 ms 141208 KB Wrong Answer[1]
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 141096 KB Output is correct
2 Correct 66 ms 141204 KB Output is correct
3 Correct 66 ms 141144 KB Output is correct
4 Correct 78 ms 141152 KB Output is correct
5 Correct 68 ms 141096 KB Output is correct
6 Correct 73 ms 141124 KB Output is correct
7 Correct 69 ms 141128 KB Output is correct
8 Correct 67 ms 141100 KB Output is correct
9 Correct 76 ms 141156 KB Output is correct
10 Correct 80 ms 141100 KB Output is correct
11 Correct 74 ms 141196 KB Output is correct
12 Correct 69 ms 141204 KB Output is correct
13 Correct 68 ms 141124 KB Output is correct
14 Incorrect 65 ms 141208 KB Wrong Answer[1]
15 Halted 0 ms 0 KB -