Submission #66069

#	Time	Username	Problem	Language	Result	Execution time	Memory
66069		khohko	Dungeon 2 (JOI16_dungeon2)	C++17	44 / 100	60 ms	49432 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[ARRS];
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();
	//cout<<k<<" = "<<lst()<<endl;
	if(k==2){mvb(); return 0;}
	n++;
	ll x=n;
	pr[x]=lst();
	if(f)v[x].pb({f,lst()});
	ll m=num();
	nm[x]=m;
	for(int i=1; i<=m; i++){
		if(i==g.top())continue;
		//cout<<x<<" -> "<<i<<endl;
		Move(i,2);
		ll k=go(x);
		if(k)v[x].pb({k,i});
			//v[k].pb(x);
		//}
	}
	mvb();
	return x;
}

ll f[400][400];
ll dp[400][400];
ll pw[100];
ll pas[100];
ll cr;

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

void dfs(ll x){
	for(auto y:v[x]){
		if(y.sc==pr[x])continue;
		Move(y.sc,gc(x));
		dfs(y.fr);
	}
	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++){
		Move(i,clr());
		f[x][i]+=(clr()-1)*pw[cr];
		Move(lst(),clr());
	}
	if(pr[x]>=0)
	Move(pr[x],clr());
}


void Inspect(int R) {

//	cout<<num()<<endl;
	//return;
	go(0);
//	for(int i=1; i<=n; i++){
//		cout<<i<<" = "<<nm[i]<<endl;
//		for(auto x:v[i])
//			cout<<x.fr<<" "<<x.sc<<endl;
//		cout<<endl;
//	}

//	cout<<num()<<endl;
	pw[0]=1;
	for(int i=1; i<10; i++)pw[i]=pw[i-1]*3;
	for(cr=0; cr<7; cr++){
		dfs(1);
		slv(1);
	}
//	cout<<endl;
//	cout<<endl;
//	cout<<"---------";
//	cout<<endl;
//	cout<<endl;
	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++){
//		cout<<nm[i]<<endl;
		for(int j=1; j<=nm[i]; j++){
//			cout<<f[i][j]<<" ";
			dp[i][f[i][j]]=1;
		}
//		cout<<endl;
	}
	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]]++;

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

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