oj.uz

답안 #134663

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
134663 2019-07-23T06:50:33 Z 임유진(#3241) Dungeon 2 (JOI16_dungeon2) C++14
44 / 100
 35 ms 1528 KB 
#include "dungeon2.h"
#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 205;

static int par[MAXN], dep[MAXN], parroad[MAXN];
static vector<int> ed[MAXN];
static int N;
static int dis[MAXN][MAXN];
static int cnt[MAXN];

int anc(int x, int d) {
	while(dep[x] > d) x = par[x];
	return x;
}

void dfs(int x) {
	int k = NumberOfRoads();
	parroad[x] = LastRoad();
	//printf("x = %d, k = %d, parroad = %d, par = %d, dep = %d\n", x, k, parroad[x], par[x], dep[x]);
	for(int i = 1; i <= k; i++) if(i != parroad[x]) {
		Move(i, 2);
		int c = Color();
		//printf("c = %d\n", c);
		if(c == 1) {
			N++;
			ed[x].push_back(N);
			ed[N].push_back(x);
			par[N] = x;
			dep[N] = dep[x] + 1;
			dfs(N);
		}
		else if(c == 2) {
			int toend = LastRoad();
			Move(toend, 1);
			int y = x;
			while(Color() != 1) {
				Move(parroad[y], 2);
				y = par[y];
			}
			ed[x].push_back(y);
			ed[y].push_back(x);
			Move(toend, 2);
		}
		else Move(LastRoad(), 3);
	}
	if(parroad[x] != -1) Move(parroad[x], 3);
}

void Inspect(int R) {
	dep[1] = 2;
	N = 1;
	dfs(1);

	/*
	for(int i = 1; i <= N; i++) {
		printf("ed[%d] = [", i);
		for(auto a : ed[i]) printf("%d ", a);
		printf("]\n");
	}
	*/

	for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) dis[i][j] = i == j ? 0 : N;
	for(int i = 1; i <= N; i++) for(auto a : ed[i]) dis[i][a] = 1;
	for(int k = 1; k <= N; k++) for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) 
		if(dis[i][k] + dis[k][j] < dis[i][j]) dis[i][j] = dis[i][k] + dis[k][j];
	//for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) printf("dis[%d][%d] = %d\n", i, j, dis[i][j]);
	for(int i = 1; i <= N; i++) for(int j = i + 1; j <= N; j++) cnt[dis[i][j]]++;
	for(int i = 1; i <= R; i++) Answer(i, cnt[i]);
}

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 3 ms 508 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 2 ms 532 KB Output is correct
14 Correct 2 ms 504 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 632 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 3 ms 548 KB Output is correct
15 Correct 3 ms 504 KB Output is correct

Subtask #3
0 / 56.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 976 KB Output is correct
2 Partially correct 16 ms 888 KB Partially correct
3 Partially correct 13 ms 888 KB Partially correct
4 Incorrect 35 ms 1528 KB Output isn't correct
5 Halted 0 ms 0 KB -