제출 #773530

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
773530		LittleCube	게임 (APIO22_game)	C++17	60 / 100	4083 ms	200176 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][7], to[300000][7], where[300000][7];
  vector<int> Ef[300000][7], Et[300000][7];
  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 + 16) / 16;
      for (int j = 1; j <= 16; 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 << 4 | (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] = 17;
    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 << 4 | (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] = 17;
    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;
}

컴파일 시 표준 에러 (stderr) 메시지

game.cpp: In function 'void init(int, int)':
game.cpp:42:17: warning: array subscript 7 is above array bounds of 'int [7]' [-Warray-bounds]
   42 |       where[j][l] = i;
      |       ~~~~~~~~~~^
game.cpp:56:16: warning: array subscript 7 is above array bounds of 'int [7]' [-Warray-bounds]
   56 |       from[L][l] = 2, to[L][l] = 1;
      |       ~~~~~~~~~^
game.cpp:56:30: warning: array subscript 7 is above array bounds of 'int [7]' [-Warray-bounds]
   56 |       from[L][l] = 2, to[L][l] = 1;
      |                       ~~~~~~~^
game.cpp:50:31: warning: array subscript 7 is above array bounds of 'int [7]' [-Warray-bounds]
   50 |           from[p][l] = to[p][l] = j;
      |                        ~~~~~~~^
game.cpp:50:20: warning: array subscript 7 is above array bounds of 'int [7]' [-Warray-bounds]
   50 |           from[p][l] = to[p][l] = j;
      |           ~~~~~~~~~^

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