Submission #773472

#	Time	Username	Problem	Language	Result	Execution time	Memory
773472		LittleCube	Game (APIO22_game)	C++17	0 / 100	105 ms	262144 KiB

game

#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][20], to[300000][20], where[300000][20];
  vector<int> Ef[300000][20], Et[300000][20];
  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: 0 / 2
• Subtask 2: 0 / 10
• Subtask 3: 0 / 18
• Subtask 4: 0 / 30
• Subtask 5: 0 / 40