Submission #641652

#	Time	Username	Problem	Language	Result	Execution time	Memory
641652		flappybird	Dungeon 2 (JOI16_dungeon2)	C++17	94 / 100	17 ms	1876 KiB

dungeon2

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

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

vector<pii> tree[MAX], up[MAX];
vector<int> backe[MAX], adj[MAX];
int prt[MAX];
int prtl[MAX];
int ans[MAX];
int dist[MAX][MAX];

int pow3[6] = { 1, 3, 9, 27, 81, 243 };

int cnt = 1;

void dfs(int x = 1, int p = 0, int pv = -1) {
	prt[x] = p;
	prtl[x] = pv;
	int deg = NumberOfRoads();
	int i;
	for (i = 1; i <= deg; i++) if (i != pv) {
		Move(i, 2);
		if (Color() == 2) backe[x].push_back(i), Move(LastRoad(), 2);
		else cnt++, tree[x].emplace_back(cnt, i), dfs(cnt, x, LastRoad());
	}
	if (x > 1) Move(pv, 2);
}

void updown(int x = 1) {
	for (auto v : backe[x]) {
		Move(v, 1);
		if (Color() == 1) up[x].emplace_back(0, v);
		Move(LastRoad(), Color());
	}
	for (auto& [v, e] : tree[x]) {
		Move(e, 1);
		updown(v);
	}
	if (x > 1) Move(prtl[x], 1);
}

int getv(int x, int k) {
	while (k--) x /= 3;
	return (x % 3) + 1;
}

void upd(int x, int k) {
	for (auto& [v, e] : tree[x]) {
		Move(e, getv(x, k));
		upd(v, k);
	}
	if (x > 1) Move(prtl[x], getv(x, k));
}

void addv(int x, int k) {
	for (auto& [v, e] : up[x]) {
		Move(e, getv(x, k));
		v += pow3[k] * (Color() - 1);
		Move(LastRoad(), Color());
	}
	for (auto& [v, e] : tree[x]) {
		Move(e, getv(x, k));
		addv(v, k);
	}
	if (x > 1) Move(prtl[x], getv(x, k));
}

void getdis(int x) {
	queue<int> q;
	q.push(x);
	while (q.size()) {
		int t = q.front();
		q.pop();
		for (auto v : adj[t]) {
			if (!dist[x][v]) {
				dist[x][v] = dist[x][t] + 1;
				q.push(v);
			}
		}
	}
}

void Inspect(int R) {
	dfs();
	updown();
	for (int k = 0; k < 6; k++) addv(1, k);
	int i, j;
	for (i = 1; i <= cnt; i++) for (auto& [v, e] : up[i]) adj[i].push_back(v), adj[v].push_back(i);
	for (i = 1; i <= cnt; i++) for (auto& [v, e] : tree[i]) adj[i].push_back(v), adj[v].push_back(i);
	for (i = 1; i <= cnt; i++) getdis(i);
	for (i = 1; i <= cnt; i++) for (j = i + 1; j <= cnt; j++) ans[dist[i][j]]++;
	for (i = 1; i <= R; i++) Answer(i, ans[i]);
}

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