Submission #26234

#	Time	Username	Problem	Language	Result	Execution time	Memory
26234		kdh9949	Dungeon 2 (JOI16_dungeon2)	C++14	100 / 100	23 ms	2232 KiB

dungeon2

#include "dungeon2.h"
#include <vector>
using namespace std;

static const int inf = 1e9, thr[5] = {1, 3, 9, 27, 81};
static int n, cnt[201], md[201][201], l[201], ln[201];
static vector<int> te[201], e[201];

void f(){
	int x = n++;
	int en = NumberOfRoads();
	for(int i = 1; i <= en; i++){
		if(i == l[x]){
			te[x].push_back(0);
			e[x].push_back(ln[x]);
			continue;
		}
		Move(i, 2);
		int b = LastRoad();
		int nc = Color();
		te[x].push_back(nc);
		if(nc == 1){
			e[x].push_back(n);
			l[n] = b;
			ln[n] = x;
			f();
			nc = 3;
		}
		else e[x].push_back(0);
		Move(b, nc);
	}
}

int get(int x, int t){ return (x / thr[t]) % 3 + 1; }

void g(int t){
	int x = n++;
	int en = NumberOfRoads();
	for(int i = 0; i < en; i++){
		if(!(te[x][i] % 3)) continue;
		Move(i + 1, get(x, t));
		int b = LastRoad();
		if(te[x][i] == 1) g(t);
		else{
			e[x][i] += (Color() - 1) * thr[t];
		}
		Move(b, Color());
	}
}

void h(int r){
	for(int i = 1; i < n; i++) fill(md[i] + 1, md[i] + n, inf);
	for(int i = 1; i < n; i++) for(auto &j : e[i]) md[i][j] = md[j][i] = 1;
	for(int k = 1; k < n; k++){
		for(int i = 1; i < n; i++){
			for(int j = 1; j < n; j++){
				md[i][j] = min(md[i][j], md[i][k] + md[k][j]);
			}
		}
	}
	for(int i = 1; i < n; i++){
		for(int j = i + 1; j < n; j++){
			cnt[md[i][j]]++;
		}
	}
	for(int i = 1; i <= r; i++) Answer(i, cnt[i]);
}

void Inspect(int R){
	n = 1;
	f();
	for(int i = 0; i < 5; i++){ n = 1; g(i); }
	h(R);
}

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