Submission #69043

#	Time	Username	Problem	Language	Result	Execution time	Memory
69043		reality	Dungeon 2 (JOI16_dungeon2)	C++17	100 / 100	42 ms	1588 KiB

dungeon2

#include "dungeon2.h"
#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define vii vector < pii >
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int N = 256;
int deg[N];
int roads[N][N];
vector < pii > g[N];
vi G[N];
int pr[N];
int D[N][N];
int ans[N];
int n;
void dfs(int node) {
	pr[node] = LastRoad();
	deg[node] = NumberOfRoads();
	for (int i = 1;i <= deg[node];++i) 
		if (pr[node] != i) {
		Move(i,2);
		int col = Color();
		if (col == 1) {
			g[node].pb(mp(i,++n));
			dfs(n);
		} else {
			if (col == 2)
				G[node].pb(i);
			Move(LastRoad(),col);
		}
	}
	if (pr[node] != -1)
		Move(pr[node],3);
}
void DFS(int node,int K) {
	for (auto it : G[node]) {
		Move(it,(node / K) % 3 + 1);
		roads[node][it] += (Color() - 1) * K;
		Move(LastRoad(),Color());
	}
	for (auto it : g[node]) {
		Move(it.fi,(node / K) % 3 + 1);
		DFS(it.se,K);
	}
	if (pr[node] != -1)
		Move(pr[node],(node / K) % 3 + 1);
}
void Inspect(int R) {
	dfs(++n);
	int pw = 1;
	for (int i = 0;i < 5;++i) {
		DFS(1,pw);
		pw *= 3;
	}
	for (int i = 1;i <= n;++i)
		for (int j = 1;j <= n;++j)
			if (i != j)
				D[i][j] = 1e9;
	for (int i = 1;i <= n;++i) {
		for (int j = 1;j <= deg[i];++j)
			if (roads[i][j])
				D[i][roads[i][j]] = D[roads[i][j]][i] = 1;
		for (auto it : g[i])
			D[i][it.se] = D[it.se][i] = 1;
	}
	for (int k = 1;k <= n;++k)
		for (int i = 1;i <= n;++i)
			for (int j = 1;j <= n;++j)
				D[i][j] = min(D[i][j],D[i][k] + D[k][j]);
	for (int i = 1;i <= n;++i)
		for (int j = 1;j < i;++j)
			if (D[i][j] <= R)
				ans[D[i][j]] += 1;
	for (int i = 1;i <= R;++i)
		Answer(i,ans[i]);
}

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