Submission #1242893

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242893		PenguinsAreCute	Dungeon 2 (JOI16_dungeon2)	C++17	100 / 100	12 ms	2116 KiB

dungeon2

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

void Inspect(int R) {
	vector<vector<pair<int,int>>> edge(6);
	vector<int> ord;
	auto dfs1 = [&ord](auto &self) mutable -> void {
		ord.push_back(0);
		int nroad = NumberOfRoads();
		for(int i=1;i<=nroad;i++) {
			ord.push_back(i);
			Move(i, 2);
			if(Color() == 1) {
				int lr = LastRoad();
				self(self);
				ord.push_back(-lr);
				Move(lr, 3);
			} else {
				if(Color() == 3)
					ord.push_back(-LastRoad());
				else
					ord.pop_back();
				Move(LastRoad(),Color());
			}
		}
	};
	dfs1(dfs1);
	for(int i=0;i<5;i++) {
		int cnt = 0;
		bool st = 0;
		for(auto op: ord) {
			if(op == 0)
				cnt++, st = 1;
			else {
				int curCol = Color();
				if(st) {
					curCol = cnt;
					for(int j=0;j<i;j++)
						curCol /= 3;
					curCol %= 3;
					curCol++;
				}
				Move(abs(op), curCol);
				if(op < 0) {
					int nwCol = Color();
					edge[i].push_back({curCol-1,nwCol-1});
				}
				st = 0;
			}
		}
	}
	for(int i=0;i<(int)edge[0].size();i++) {
		edge[5].push_back({0,0});
		for(int j=0,p3=1;j<5;j++,p3*=3) {
			edge[5][i].first += (edge[j][i].first * p3);
			edge[5][i].second += (edge[j][i].second * p3);
		}
	}
	int N = 0;
	for(auto [x, y]: edge[5])
		N = max({N,x,y});
	N++;
	int dist[N][N];
	memset(dist,1,sizeof(dist));
	for(auto [x, y]: edge[5])
		dist[x][y] = dist[y][x] = 1;
	for(int i=0;i<N;i++)
		dist[i][i] = 0;
	for(int k=0;k<N;k++)
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++)
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); 
	int res[R+1];
	memset(res,0,sizeof(res));
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
			if(dist[i][j]<=R)
				res[dist[i][j]]+=1;
	for(int i=1;i<=R;i++)
		Answer(i,res[i]/2);
}

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