Submission #66091

#	Time	Username	Problem	Language	Result	Execution time	Memory
66091		khohko	Dungeon 2 (JOI16_dungeon2)	C++17	90 / 100	40 ms	3952 KiB

dungeon2

#include "dungeon2.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fr first
#define sc second
#define ARRS ((ll)(2e6+100))
#define MAX ((ll)(1e9+100))
#define MOD ((ll)(1e9+7))

//void Inspect(int R);
//void Answer(int D, int A);
//void Move(int I, int V);
//int NumberOfRoads();
//int LastRoad();
//int Color();
#define num NumberOfRoads
#define lst LastRoad
#define clr Color

stack<ll> g;
vector<pair<ll,ll> > v[400];
ll C=1;
ll pr[400];
ll nm[400];
void mvb(){
	ll t=g.top();
	g.pop();
	if(t>=0)Move(t,2);
}

ll n=0;

ll go(ll f){
	g.push(LastRoad());
	ll k=Color();
	if(k==2){mvb(); return 0;}
	n++;
	ll x=n;
	pr[x]=lst();
	if(f)v[x].pb({f,pr[x]});
	ll m=num();
	nm[x]=m;
	for(int i=1; i<=m; i++){
		if(i==g.top())continue;
		Move(i,2);
		ll k=go(x);
		if(k)v[x].pb({k,i});
	}
	mvb();
	return x;
}

ll f[400][400];
ll ef[700][700];
ll dp[400][400];
ll bk[400][400];
ll pw[400];
ll pas[400];
ll cr;

ll gc(ll x){
	return (x/pw[cr])%3+1;
}
ll gcc(ll x){
	return (x/pw[cr+1])%3+1;
}

vector<ll> ord;
ll out[400];
void dfs(ll x){
	for(auto y:v[x]){
		if(y.sc==pr[x])continue;
		Move(y.sc,gc(x));
		dfs(y.fr);
	}
	ord.pb(x);
	if(pr[x]>=0)
	Move(pr[x],gc(x));
}

void slv(ll x){
	for(auto y:v[x]){
		if(y.sc==pr[x])continue;
		Move(y.sc,clr());
		slv(y.fr);
	}
	for(int i=1; i<=num(); i++){
		if(ef[x][i])continue;
		Move(i,clr());
		f[x][i]+=(clr()-1)*pw[cr];
		bk[x][i]=lst();
		Move(lst(),clr());
	}
	if(pr[x]>=0)
	Move(pr[x],gcc(x));
	else {
		Move(1,gcc(x));
		Move(lst(),clr());
	}
}


void Inspect(int R) {
	go(0);

	for(int i=1; i<=n; i++){
		for(auto x:v[i]){
			ef[i][x.sc]=1;
			f[i][x.sc]=x.fr;
		}
	}

	pw[0]=1;
	for(int i=1; i<15; i++)pw[i]=pw[i-1]*3;
	dfs(1);
	for(cr=0; cr<5; cr++)
		slv(1);

	for(auto i:ord)
		for(int j=1; j<=nm[i]; j++){
			if(ef[i][j])continue;
			//if(out[i]<=out[f[i][j]])
			f[f[i][j]][bk[i][j]]=i;
		}

	for(int i=1; i<=n; i++)
		for(int j=1; j<=n; j++)
			dp[i][j]=MAX;

	for(int i=1; i<=n; i++)
		for(int j=1; j<=nm[i]; j++)
			dp[i][f[i][j]]=1;

	for(int k=1; k<=n; k++)
		for(int i=1; i<=n; i++)
			for(int j=1; j<=n; j++)
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);

	for(int i=1; i<=n; i++)
		for(int j=i+1; j<=n; j++)
			pas[dp[i][j]]++;

	for(int i = 1; i <= R; i++)
		Answer(i, pas[i]);
}

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