oj.uz

Submission #773475

# Submission time Handle Problem Language Result Execution time Memory
773475 2023-07-05T05:54:31 Z LittleCube Game (APIO22_game) C++17
2 / 100
 124 ms 239956 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][17], to[300000][17], where[300000][17];
  vector<int> Ef[300000][17], Et[300000][17];
  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 106 ms 239780 KB Output is correct
2 Correct 108 ms 239740 KB Output is correct
3 Correct 107 ms 239808 KB Output is correct
4 Correct 124 ms 239716 KB Output is correct
5 Correct 108 ms 239800 KB Output is correct
6 Correct 109 ms 239744 KB Output is correct
7 Correct 108 ms 239816 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 239780 KB Output is correct
2 Correct 108 ms 239740 KB Output is correct
3 Correct 107 ms 239808 KB Output is correct
4 Correct 124 ms 239716 KB Output is correct
5 Correct 108 ms 239800 KB Output is correct
6 Correct 109 ms 239744 KB Output is correct
7 Correct 108 ms 239816 KB Output is correct
8 Correct 109 ms 239840 KB Output is correct
9 Correct 109 ms 239804 KB Output is correct
10 Correct 110 ms 239820 KB Output is correct
11 Correct 108 ms 239848 KB Output is correct
12 Correct 109 ms 239788 KB Output is correct
13 Correct 113 ms 239956 KB Output is correct
14 Incorrect 112 ms 239836 KB Wrong Answer[1]
15 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 239780 KB Output is correct
2 Correct 108 ms 239740 KB Output is correct
3 Correct 107 ms 239808 KB Output is correct
4 Correct 124 ms 239716 KB Output is correct
5 Correct 108 ms 239800 KB Output is correct
6 Correct 109 ms 239744 KB Output is correct
7 Correct 108 ms 239816 KB Output is correct
8 Correct 109 ms 239840 KB Output is correct
9 Correct 109 ms 239804 KB Output is correct
10 Correct 110 ms 239820 KB Output is correct
11 Correct 108 ms 239848 KB Output is correct
12 Correct 109 ms 239788 KB Output is correct
13 Correct 113 ms 239956 KB Output is correct
14 Incorrect 112 ms 239836 KB Wrong Answer[1]
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 239780 KB Output is correct
2 Correct 108 ms 239740 KB Output is correct
3 Correct 107 ms 239808 KB Output is correct
4 Correct 124 ms 239716 KB Output is correct
5 Correct 108 ms 239800 KB Output is correct
6 Correct 109 ms 239744 KB Output is correct
7 Correct 108 ms 239816 KB Output is correct
8 Correct 109 ms 239840 KB Output is correct
9 Correct 109 ms 239804 KB Output is correct
10 Correct 110 ms 239820 KB Output is correct
11 Correct 108 ms 239848 KB Output is correct
12 Correct 109 ms 239788 KB Output is correct
13 Correct 113 ms 239956 KB Output is correct
14 Incorrect 112 ms 239836 KB Wrong Answer[1]
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 239780 KB Output is correct
2 Correct 108 ms 239740 KB Output is correct
3 Correct 107 ms 239808 KB Output is correct
4 Correct 124 ms 239716 KB Output is correct
5 Correct 108 ms 239800 KB Output is correct
6 Correct 109 ms 239744 KB Output is correct
7 Correct 108 ms 239816 KB Output is correct
8 Correct 109 ms 239840 KB Output is correct
9 Correct 109 ms 239804 KB Output is correct
10 Correct 110 ms 239820 KB Output is correct
11 Correct 108 ms 239848 KB Output is correct
12 Correct 109 ms 239788 KB Output is correct
13 Correct 113 ms 239956 KB Output is correct
14 Incorrect 112 ms 239836 KB Wrong Answer[1]
15 Halted 0 ms 0 KB -