oj.uz

Submission #134571

# Submission time Handle Problem Language Result Execution time Memory
134571 2019-07-23T04:10:29 Z 임유진(#3241) None (JOI16_dungeon2) C++14
17 / 100
 3 ms 760 KB 
#include "dungeon2.h"
#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 105;

static int par[MAXN], dep[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();
	int l = LastRoad();
	//printf("x = %d, k = %d, l = %d, par = %d, dep = %d\n", x, k, l, par[x], dep[x]);
	for(int i = 1; i <= k; i++) if(i != l) {
		Move(i, dep[x]);
		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 {
			Move(LastRoad(), c);
			if(c < dep[x]) {
				int y = anc(x, c);
				//printf("x = %d, y = %d\n", x, y);
				ed[x].push_back(y);
				ed[y].push_back(x);
			}
		}
	}
	if(l != -1) Move(l, dep[x]);
}

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 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 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 504 KB Output is correct
12 Correct 2 ms 504 KB Output is correct
13 Correct 2 ms 504 KB Output is correct
14 Correct 3 ms 504 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 760 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -