Submission #210324

#	Time	Username	Problem	Language	Result	Execution time	Memory
210324		EntityIT	Dungeon 2 (JOI16_dungeon2)	C++14	100 / 100	23 ms	1400 KiB

dungeon2

#include "dungeon2.h"
#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

template<class T>
inline bool asMn(T &a, const T &b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T &a, const T &b) { return a < b ? a = b, true : false; }

const int LIM = 243;// 3 ^ 5
const int inf = 1e9;
mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() );

vector<vector<int> > gr;

int buildTree() {
  if (Color() ^ 1) {
    int ret = Color();
    Move(LastRoad(), ret);
    return -ret;
  }

  int u = sz(gr); gr.emplace_back(vector<int>(NumberOfRoads() ) );
  int prv = LastRoad() - 1;
  for (int i = 0; i < sz(gr[u]); ++i) {
    if (i ^ prv) {
      Move(i + 1, 2);
      int tmp = buildTree();
      if (tmp < 0) gr[u][i] = tmp;
      else gr[u][i] = tmp;
    }
    else gr[u][i] = -1;
  }

  if (u) Move(prv + 1, 3);
  return u;
}

array<int, 5> pw3{ 1, 3, 9, 27, 81 };

int get(int a, int k) {
  a /= pw3[k];
  int ret = 0;
  while (a % 3) ++ret, --a;
  return ret;
}

void solve(int u, int k) {
  int c = get(u, k) + 1;
  for (int i = 0; i < sz(gr[u]); ++i) {
    if (gr[u][i] >= 0) {
      Move(i + 1, c);
      solve(gr[u][i], k);
    }
    else if (gr[u][i] < -3) {
      Move(i + 1, c);
      int coef = Color() - 1;
      gr[u][i] += pw3[k] * coef;
      Move(LastRoad(), coef + 1);
    }
  }

  if (u) Move( (int)(find(all(gr[u]), -1) - gr[u].begin() ) + 1, c);
}

void Inspect(int R) {
  buildTree();
  for (auto &i : gr) {
    for (auto &j : i) if (j == -2) j = -LIM;
  }
  solve(0, 0);
  solve(0, 1);
  solve(0, 2);
  solve(0, 3);
  solve(0, 4);

  vector<vector<int> > d(sz(gr), vector<int>(sz(gr), inf) );
  for (int u = 0; u < sz(gr); ++u) {
    d[u][u] = 0;
    for (int i = 0; i < sz(gr[u]); ++i) {
      if (gr[u][i] < -3) gr[u][i] += LIM;
      if (gr[u][i] >= 0) d[u][ gr[u][i] ] = d[ gr[u][i] ][u] = 1;
    }
  }

  for (int k = 0; k < sz(gr); ++k) {
    for (int i = 0; i < sz(gr); ++i) {
      for (int j = 0; j < sz(gr); ++j) asMn(d[i][j], d[i][k] + d[k][j]);
    }
  }

  vector<int> ans(R);
  for (int u = 0; u < sz(gr); ++u) {
    for (int v = u + 1; v < sz(gr); ++v) if (d[u][v] <= R) ++ans[ d[u][v] - 1 ];
  }
  for (int i = 0; i < R; ++i) Answer(i + 1, ans[i]);
}

• Subtask 1: 17 / 17
• Subtask 2: 27 / 27
• Subtask 3: 56 / 56