Submission #55858

#	Time	Username	Problem	Language	Result	Execution time	Memory
55858		khsoo01	Dungeon 2 (JOI16_dungeon2)	C++11	100 / 100	35 ms	1532 KiB

dungeon2

#include "dungeon2.h"
#include<bits/stdc++.h>
using namespace std;

const int N = 205, inf = 1e9;

int n, bas = 1, dis[N][N], ans[N];

vector<int> adj[N], bck[N];

void build (int I) {
	int K = NumberOfRoads();
	int L = LastRoad();
	for(int i=0;i<K;i++) {
		if(i+1 == L) {
			adj[I].push_back(0);
			bck[I].push_back(2);
			continue;
		}
		Move(i+1, 2);
		if(Color() > 1) {
			adj[I].push_back(0);
			bck[I].push_back(Color() - 1);
			Move(LastRoad(), Color());
		}
		else {
			adj[I].push_back(++n);
			bck[I].push_back(0);
			build(n);
		}
	}
	if(~L) Move(L, 3);
}

void seek (int I) {
	int K = adj[I].size();
	int V = I / bas % 3;
	int L = LastRoad();
	for(int i=0;i<K;i++) {
		if(bck[I][i] == 2) continue;
		Move(i+1, V+1);
		if(bck[I][i]) {
			adj[I][i] += (Color()-1) * bas;
			Move(LastRoad(), Color());
		}
		else {
			seek(adj[I][i]);
		}
	}
	if(I != 1) Move(L, 1);
}

void Inspect(int R)
{
	build(++n);
	for(int i=0;i<5;i++) {
		seek(1);
		bas *= 3;
	}
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			dis[i][j] = inf;
		}
		dis[i][i] = 0;
	}
	for(int i=1;i<=n;i++) {
		for(auto &T : adj[i]) {
			if(!T) continue;
			dis[i][T] = 1;
			dis[T][i] = 1;
		}
	}
	for(int k=1;k<=n;k++) {
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				if(dis[i][k] + dis[k][j] < dis[i][j]) {
					dis[i][j] = dis[i][k] + dis[k][j];
				}
			}
		}
	}
	for(int i=1;i<=n;i++) {
		for(int j=i+1;j<=n;j++) {
			ans[dis[i][j]]++;
		}
	}
	for(int i=1;i<=R;i++) {
		Answer(i, ans[i]);
	}
}

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