답안 #39812

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
39812 2018-01-19T11:35:37 Z aome Dungeon 2 (JOI16_dungeon2) C++14
100 / 100
36 ms 3284 KB
#include "dungeon2.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> ii;

const int N = 205;
const int INF = 0x3f3f3f3f;

const int pw3[] = {1, 3, 9, 27, 81}; 

int n, node;
int sz[N], par[N];
int edge[N][N], anc[N][N];
int bit3[N][5];
int dis[N][N], res[N];
vector<ii> G[N];

void dfs() {
	node = n++;
	int par_edge = LastRoad();
	sz[node] = NumberOfRoads();
	for (int i = 1; i <= sz[node]; ++i) {
		if (i == par_edge) continue;
		Move(i, 2);
		int color = Color();
		if (color > 1) {
			int tmp = LastRoad();
			Move(tmp, color);
			edge[node][i] = color;
		}
		else {
			par[n] = node, G[node].push_back(ii(n, i)), dfs();
		}
	}
	if (par_edge != -1) {
		Move(par_edge, 3), node = par[node];
	}
}

void dfs2(int u, int x) {
	int coloru = bit3[u][x] + 1;
	int par_edge;
	if (u) par_edge = LastRoad();
	for (int i = 1; i <= sz[u]; ++i) {
		if (edge[u][i] == 2) {
			Move(i, coloru);
			int colorp, last_road;
			colorp = Color(), anc[u][i] += pw3[x] * (colorp - 1);
			last_road = LastRoad(), Move(last_road, colorp);
		} 
	}
	for (auto i : G[u]) {
		Move(i.second, coloru), dfs2(i.first, x);
	}
	if (u) Move(par_edge, coloru);
} 

void Inspect(int R) {
	dfs();
	for (int i = 0; i < n; ++i) {
		int cur = i;
		for (int j = 0; j < 5; ++j) {
			bit3[i][j] = cur % 3, cur /= 3;
		}
	}
	for (int i = 0; i < 5; ++i) dfs2(0, i);
	memset(dis, INF, sizeof dis);
	for (int i = 0; i < n; ++i) {
		for (int j = 1; j <= sz[i]; ++j) {
			if (edge[i][j] == 2) G[i].push_back(ii(anc[i][j], j));
		}
		dis[i][i] = 0;
		for (auto j : G[i]) {
			dis[i][j.first] = dis[j.first][i] = 1;
		}
	}
	for (int k = 0; k < n; ++k) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < i; ++j) {
			res[dis[i][j]]++;
		}
	}
	for (int i = 1; i <= R; ++i) Answer(i, res[i]);
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 3020 KB Output is correct
2 Correct 1 ms 3020 KB Output is correct
3 Correct 0 ms 3020 KB Output is correct
4 Correct 1 ms 3020 KB Output is correct
5 Correct 1 ms 3020 KB Output is correct
6 Correct 0 ms 3020 KB Output is correct
7 Correct 1 ms 3020 KB Output is correct
8 Correct 0 ms 3020 KB Output is correct
9 Correct 1 ms 3020 KB Output is correct
10 Correct 0 ms 3020 KB Output is correct
11 Correct 1 ms 3020 KB Output is correct
12 Correct 1 ms 3020 KB Output is correct
13 Correct 1 ms 3020 KB Output is correct
14 Correct 1 ms 3020 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 3020 KB Output is correct
2 Correct 1 ms 3020 KB Output is correct
3 Correct 0 ms 3020 KB Output is correct
4 Correct 0 ms 3020 KB Output is correct
5 Correct 1 ms 3020 KB Output is correct
6 Correct 1 ms 3020 KB Output is correct
7 Correct 0 ms 3020 KB Output is correct
8 Correct 1 ms 3020 KB Output is correct
9 Correct 1 ms 3020 KB Output is correct
10 Correct 1 ms 3020 KB Output is correct
11 Correct 1 ms 3020 KB Output is correct
12 Correct 1 ms 3020 KB Output is correct
13 Correct 0 ms 3020 KB Output is correct
14 Correct 1 ms 3020 KB Output is correct
15 Correct 1 ms 3020 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 3020 KB Output is correct
2 Correct 11 ms 3020 KB Output is correct
3 Correct 13 ms 3020 KB Output is correct
4 Correct 24 ms 3284 KB Output is correct
5 Correct 1 ms 3020 KB Output is correct
6 Correct 4 ms 3020 KB Output is correct
7 Correct 11 ms 3020 KB Output is correct
8 Correct 11 ms 3020 KB Output is correct
9 Correct 6 ms 3020 KB Output is correct
10 Correct 11 ms 3020 KB Output is correct
11 Correct 11 ms 3020 KB Output is correct
12 Correct 14 ms 3020 KB Output is correct
13 Correct 10 ms 3152 KB Output is correct
14 Correct 11 ms 3020 KB Output is correct
15 Correct 11 ms 3020 KB Output is correct
16 Correct 4 ms 3152 KB Output is correct
17 Correct 19 ms 3284 KB Output is correct
18 Correct 24 ms 3284 KB Output is correct
19 Correct 36 ms 3284 KB Output is correct