Submission #773551

#	Time	Username	Problem	Language	Result	Execution time	Memory
773551		LittleCube	Game (APIO22_game)	C++17	100 / 100	3761 ms	251600 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
{
  const int P = 10;
  int n, k, from[300000][8], to[300000][8], where[300000][8];
  vector<int> Ef[300000][8], Et[300000][8];
  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;
}

• Subtask 1: 2 / 2
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 30 / 30
• Subtask 5: 40 / 40