Submission #849288

#	Time	Username	Problem	Language	Result	Execution time	Memory
849288		mickey080929	Dungeon 2 (JOI16_dungeon2)	C++17	100 / 100	17 ms	1376 KiB

dungeon2

#include "dungeon2.h"
#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> pii;

const int inf = 1e9;

pii par[210];
vector<pii> up[210];
vector<pii> down[210];
int n;
int dist[210][210];
int ans[210];

int make_dfs_tree(int p) {
    if (Color() == 2) {
        Move(LastRoad(), 2);
        return 0;
    }
    if (Color() == 3) {
        Move(LastRoad(), 3);
        return -1;
    }
    int x = ++ n;
    par[x] = {LastRoad(), p};
    int deg = NumberOfRoads();
    for (int i=1; i<=deg; i++) {
        if (i == par[x].first) continue;
        Move(i, 2);
        int ret = make_dfs_tree(x);
        if (ret == 0) up[x].emplace_back(i, 0);
        else if (ret > 0) down[x].emplace_back(i, ret);
    }
    if (x != 1) Move(par[x].first, 3);
    return x;
}

void dfs(int x, int step) {
    for (auto &[road, num] : up[x]) {
        Move(road, 1);
        num = num + (Color() - 1) * step;
        Move(LastRoad(), Color());
    }
    int digit = x / step % 3;
    for (auto &[road, num] : down[x]) {
        Move(road, digit+1);
        dfs(num, step);
    }
    if (x != 1) Move(par[x].first, 1);
}

void Inspect(int R) {
	make_dfs_tree(-1);
	int step = 1;
	for (int i=0; i<5; i++) dfs(1, step), step *= 3;
	for (int i=1; i<=n; i++)
        for (int j=i+1; j<=n; j++)
            dist[i][j] = dist[j][i] = inf;
	for (int i=1; i<=n; i++) {
        for (auto &[road, num] : up[i])
            dist[i][num] = dist[num][i] = 1;
        if (i != 1)
            dist[i][par[i].second] = dist[par[i].second][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++)
            ans[dist[i][j]] ++;
    for (int i=1; i<=R; i++)
        Answer(i, ans[i]);
}

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