Submission #55117

#	Time	Username	Problem	Language	Result	Execution time	Memory
55117		ainta	Dungeon 2 (JOI16_dungeon2)	C++17	100 / 100	27 ms	1536 KiB

dungeon2

#include "dungeon2.h"
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define N_ 210

int cnt = 0, par[N_], pE[N_], C[N_], S[N_][N_], E[N_][N_], v[N_][N_];
vector<int>Up[N_], Ch[N_], ChN[N_];

void DFS() {
	int a = ++cnt;
	C[a] = NumberOfRoads();
	pE[a] = LastRoad();
	int i;
	for (i = 1; i <= C[a]; i++) {
		if (pE[a] == i)continue;
		Move(i, 2);
		int c = Color();
		if (c == 1) {
			par[cnt + 1] = a;
			Ch[a].push_back(i);
			ChN[a].push_back(cnt + 1);
			DFS();
		}
		else if (c == 2) {
			Up[a].push_back(i);
			Move(LastRoad(), 2);
		}
		else {
			Move(LastRoad(), 3);
		}
	}
	if (pE[a] != -1) {
		Move(pE[a], 3);
	}
}
int po[6], res[N_];

void Go(int a, int K) {
	for (auto &x : Up[a]) {
		Move(x, 1);
		S[a][x] += (Color()-1)*K;
		Move(LastRoad(), Color());
	}
	for (int i = 0; i < Ch[a].size(); i++) {
		Move(Ch[a][i], (a / K) % 3 + 1);
		Go(ChN[a][i], K);
	}
	if (pE[a] != -1)Move(pE[a], (a / K) % 3 + 1);
}

void Inspect(int R)
{
	DFS();
	po[0] = 1;
	int i, j, k;
	for (i = 0; i < 5; i++)po[i + 1] = po[i] * 3;
	for (i = 0; i < 5; i++) {
		Go(1, po[i]);
	}
	for (i = 1; i <= cnt; i++)for (j = 1; j <= cnt; j++) {
		if (i != j)E[i][j] = 1e9;
		else E[i][j] = 0;
	}
	for (i = 2; i <= cnt; i++) {
		E[i][par[i]] = E[par[i]][i] = 1;
	}
	for (i = 1; i <= cnt; i++) {
		for (auto &x : Up[i]) {
			E[i][S[i][x]] = E[S[i][x]][i] = 1;
		}
	}
	for (k = 1; k <= cnt; k++)for (i = 1; i <= cnt; i++)for (j = 1; j <= cnt; j++)E[i][j] = min(E[i][j], E[i][k] + E[k][j]);
	for (i = 1; i <= cnt; i++)for (j = i + 1; j <= cnt; j++) {
		res[E[i][j]]++;
	}
	for (i = 1; i <= R; i++) {
		Answer(i, res[i]);
	}
}

Compilation message (stderr)

dungeon2.cpp: In function 'void Go(int, int)':
dungeon2.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < Ch[a].size(); i++) {
                  ~~^~~~~~~~~~~~~~

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