Submission #39296

#	Time	Username	Problem	Language	Result	Execution time	Memory
39296		funcsr	Dungeon 2 (JOI16_dungeon2)	C++14	100 / 100	26 ms	3100 KiB

dungeon2

#include "dungeon2.h"
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <cassert>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x), x.end()))
#define index(x, y) (int)(lower_bound(all(x), y) - x.begin())
#define pb push_back
#define _1 first
#define _2 second
#define INF 1145141919

int N;
int G[200][200];
int deg[200];
int pe[200];
int to[200][200];

void dfs(int x, int p) {
  deg[x] = NumberOfRoads();
  pe[x] = max(-1, LastRoad()-1);
  if (pe[x] != -1) G[x][pe[x]] = p;
  rep(e, deg[x]) if (e != pe[x]) {
    Move(e+1, 2);
    int c = Color(), back = LastRoad()-1;
    if (c != 1) {
      if (c == 3) G[x][e] = -2;
      else G[x][e] = -1;
      Move(back+1, c);
    }
    else {
      int t = N++;
      G[x][e] = t;
      dfs(t, x);
      Move(back+1, 3);
    }
  }
}
void dfs2(int x, int k) {
  int val = x;
  rep(i, k) val /= 3;
  val = (val%3)+1;

  rep(e, deg[x]) if (e != pe[x]) {
    if (G[x][e] == -2) continue;
    Move(e+1, val);
    int c = Color(), back = LastRoad()-1;
    if (G[x][e] == -1) {
      int v = c-1;
      rep(i, k) v *= 3;
      to[x][e] += v;
      Move(back+1, c);
    }
    else {
      dfs2(G[x][e], k);
    }
  }
  if (pe[x] != -1) Move(pe[x]+1, val);
}

vector<int> G2[200];
int D[200];
int ans[201];

void Inspect(int R) {
  rep(i, 200) rep(j, 200) G[i][j] = -1;
  N = 1;
  dfs(0, -1); // 4M
  assert(N <= 200);
  rep(i, 5) dfs2(0, i); // 2M*5
  rep(x, N) {
    rep(e, deg[x]) {
      if (G[x][e] >= 0) {
        int t = G[x][e];
        G2[x].pb(t);
      }
      if (G[x][e] == -1) {
        int t = to[x][e];
        assert(t < x);
        G2[x].pb(t);
        G2[t].pb(x);
      }
    }
  }
  rep(s, N) {
    queue<int> q;
    rep(i, N) D[i] = INF;
    D[s] = 0;
    q.push(s);
    while (!q.empty()) {
      int x = q.front(); q.pop();
      for (int t : G2[x]) {
        if (D[t] == INF) {
          D[t] = D[x]+1;
          q.push(t);
        }
      }
    }
    rep(i, N) ans[D[i]]++;
  }
  rep(i, R) Answer(i+1, ans[i+1]/2);
}

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