Submission #211817

#	Time	Username	Problem	Language	Result	Execution time	Memory
211817		youngyojun	Dungeon 2 (JOI16_dungeon2)	C++11	100 / 100	29 ms	3576 KiB

dungeon2

#include "dungeon2.h"
#include <bits/stdc++.h>
#define pb push_back
#define sz(V) ((int)(V).size())
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;
 
const int MAXN = 205;
 
vector<int> G[MAXN];
vector<bool> GD[MAXN];
vector<vector<int>> GC[MAXN];
 
int D[MAXN][MAXN];
int Ans[MAXN];
 
int N, K, CDG;
 
int getColor(int n, int k) {
	for(; k; k--) n /= 3;
	return n % 3 + 1;
}
 
int getIndex(vector<int> &V) {
	int ret = 0;
	for(int k = 4; 0 <= k; k--)
		ret = ret * 3 + (V[k] - 1);
	return ret;
}
 
int f(int pv) {
	const int idx = ++N;
	const int dg = NumberOfRoads();
	const int li = LastRoad();
	G[idx].resize(dg+1, 0);
	GD[idx].resize(dg+1, false);
	GC[idx].resize(dg+1, vector<int>(6, 0));
 
	if(1 <= li && 1 <= pv) {
		G[idx][li] = pv;
	}
 
	for(int i = 1; i <= dg; i++) {
		if(G[idx][i]) continue;
 
		Move(i, 2);
		if(2 == Color()) {
			G[idx][i] = -1;
			GD[idx][i] = true;
			Move(LastRoad(), 2);
			continue;
		} else if(3 == Color()) {
			G[idx][i] = -2;
			GD[idx][i] = true;
			Move(LastRoad(), 3);
			continue;
		}
 
		G[idx][i] = f(idx);
	}
 
	if(1 <= li) Move(li, 3);
	return idx;
}
 
void g(int idx, int pv) {
	const int dg = NumberOfRoads();
	const int col = getColor(idx, CDG);
	const int li = LastRoad();
 
	for(int i = 1; i <= dg; i++) {
		if(pv == G[idx][i]) continue;
		if(-2 == G[idx][i]) continue;
		if(1 <= G[idx][i]) {
			if(GD[idx][i]) continue;
			Move(i, col);
			g(G[idx][i], idx);
			continue;
		}
 
		Move(i, col);
		GC[idx][i][CDG] = Color();
 
		if(4 == CDG) {
			const int nidx = getIndex(GC[idx][i]);
			G[nidx][LastRoad()] = idx;
			G[idx][i] = nidx;
		}
 
		Move(LastRoad(), Color());
	}
 
	if(1 != idx && 1 <= li)
		Move(li, col);
}
 
void Inspect(int K) {
	::K = K;
	f(-1);
 
	for(int i = 0; i < 5; i++) {
		CDG = i;
		g(1, -INF);
	}

	for(int i = 1; i <= N; i++) fill(D[i], D[i]+N+1, INF);
	for(int i = 1; i <= N; i++) D[i][i] = 0;
	for(int i = 1; i <= N; i++) {
		for(int v : G[i]) {
			if(v < 1 || N < v) continue;
			D[i][v] = D[v][i] = 1;
		}
	}
 
	for(int k = 1; k <= N; k++) for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++)
		upmin(D[i][j], D[i][k] + D[k][j]);
	
	for(int i = 1; i <= N; i++) for(int j = i+1; j <= N; j++)
		Ans[D[i][j]]++;
	
	for(int i = 1; i <= K; i++)
		Answer(i, Ans[i]);
}

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