oj.uz

답안 #27139

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
27139 2017-07-09T14:27:52 Z abcdef6199 Dungeon 2 (JOI16_dungeon2) C++
0 / 100
 16 ms 2868 KB 
#include "dungeon2.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> II;

const int MAXN = 200 + 10;
int n, a[MAXN][MAXN];
int ans[MAXN][MAXN];
vector<II> adj[MAXN];
vector<int> ret[MAXN];

void Build(int u) {
	int deg = NumberOfRoads();
	int pre = LastRoad();
	for (int i = 1; i <= deg; ++i) if (i != pre) {
		Move(i, 2);
		int x = LastRoad();
		if (Color() == 1) {
			// cout << "#" << u << " " << n + 1 << endl;
			adj[u].push_back(II(++n, i));
			Build(n);
		}
		else if (Color() == 2) {
			ret[u].push_back(i);
		}
		Move(x, 3);
	}
}

void DFS(int u, int pw, vector<int> ver) {
	int h = (int) ver.size();
	for (int j = 0; j < (int) ret[u].size(); ++j) {
		int i = ret[u][j];
		Move(i, h % (pw * 3) / pw + 1);
		int x = LastRoad();
		int c = Color();
		ans[u][i] += pw * (c - 1);
		Move(x, c);
		if (pw == 81) {
			int v = ver[ans[u][i]];
			a[u][v] = 1;
			a[v][u] = 1;
		}
	}
	ver.push_back(u);
	for (int j = 0; j < (int) adj[u].size(); ++j) {
		int i = adj[u][j].second;
		Move(i, h % (pw * 3) / pw + 1);
		int x = LastRoad();
		DFS(adj[u][j].first, pw, ver);
		Move(x, Color());
	}
	ver.pop_back();
}

void Inspect(int R) {
	n = 1; Build(1);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) a[i][j] = 100000;
		a[i][i] = 0;
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < (int) adj[i].size(); ++j) {
			int x = adj[i][j].first;
			a[i][x] = 1;
			a[x][i] = 1;
		}
	}
	DFS(1,  1, vector<int>(0, 0));
	DFS(1,  3, vector<int>(0, 0));
	DFS(1,  9, vector<int>(0, 0));
	DFS(1, 27, vector<int>(0, 0));
	DFS(1, 81, vector<int>(0, 0));

	// for (int i = 1; i <= n; ++i) {
	// 	for (int j = 1; j <= n; ++j) printf("%d ", a[i][j]);
	// 	puts("");
	// }
	for (int k = 1; k <= n; ++k)
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= n; ++j)
				a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
	// for (int i = 1; i <= n; ++i) {
	// 	for (int j = 1; j <= n; ++j) printf("%d ", a[i][j]);
	// 	puts("");
	// }
	for (int i = 1; i <= R; ++i) {
		int ans = 0;
		for (int u = 1; u <= n; ++u)
			for (int v = u + 1; v <= n; ++v)
				if (a[u][v] == i) ans++;
		Answer(i, ans);
	}
}

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2868 KB Output is correct
2 Correct 0 ms 2868 KB Output is correct
3 Correct 0 ms 2868 KB Output is correct
4 Incorrect 0 ms 2868 KB Wrong Answer [4]
5 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 2868 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 2868 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -