Submission #26129

#	Time	Username	Problem	Language	Result	Execution time	Memory
26129		khsoo01	Dungeon 2 (JOI16_dungeon2)	C++11	100 / 100	23 ms	2948 KiB

dungeon2

#include "dungeon2.h"
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;
const int inf = 1e9;

int n, bck[205], cur = 1;
int dist[205][205], ans[205];

vector<pii> adj[205];

void init (int C, int P) {
	adj[C].resize(NumberOfRoads()+1);
	if(P) {
		bck[C] = LastRoad();
		adj[C][bck[C]] = pii(P, 1);
	}
	for(int i=1;i<adj[C].size();i++) {
		if(i == bck[C]) continue;
		Move(i, 2);
		if(Color() != 1) {
			adj[C][i] = pii(0, Color());
			Move(LastRoad(), Color());
		}
		else {
			adj[C][i] = pii(++n, 0);
			init(n, C);
		}
	}
	if(P) Move(bck[C], 3);
}

void getbit (int C, int P) {
	for(int i=1;i<adj[C].size();i++) {
		if(adj[C][i].Y == 0) {
			Move(i, (C/cur)%3+1);
			getbit(adj[C][i].X, C);
		}
		if(adj[C][i].Y == 2) {
			Move(i, 1);
			adj[C][i].X += (Color()-1)*cur;
			Move(LastRoad(), Color());
		}
	}
	if(P) Move(bck[C], 1);
}

void Inspect(int R)
{
	init(++n, 0);
	for(int i=0;i<5;i++) {
		getbit(1, 0);
		cur *= 3;
	}
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) dist[i][j] = inf;
		dist[i][i] = 0;
	}
	for(int i=1;i<=n;i++) for(auto &T : adj[i]) {
		int A, B; tie(A, B) = T;
		if(B % 2) continue;
		dist[i][A] = 1; dist[A][i] = 1;
	}
	for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) {
		dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
	}
	for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) {
		if(dist[i][j] <= R) ans[dist[i][j]]++;
	}
	for(int i=1;i<=R;i++) Answer(i, ans[i]);
}

Compilation message (stderr)

dungeon2.cpp: In function 'void init(int, int)':
dungeon2.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<adj[C].size();i++) {
               ^
dungeon2.cpp: In function 'void getbit(int, int)':
dungeon2.cpp:36:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<adj[C].size();i++) {
               ^

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