Submission #191993

#	Time	Username	Problem	Language	Result	Execution time	Memory
191993		dndhk	Dungeon 2 (JOI16_dungeon2)	C++14	94 / 100	32 ms	1940 KiB

dungeon2

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

#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 200;
const int INF = 1000;

vector<pii> gp[MAX_N+1];
vector<int> gp2[MAX_N+1];
vector<int> to[MAX_N+1];
vector<int> s[MAX_N+1], e[MAX_N+1];
pii p[MAX_N+1];
int deg[MAX_N+1];
int N = 1;
bool chk[MAX_N+1];

void dfs1(int x){
	//cout<<x<<endl;
	deg[x] = NumberOfRoads();
	for(int i=0; i<=deg[x]; i++){
		to[x].pb(0);
		s[x].pb(0); e[x].pb(0);
	}
	if(x!=1){
		p[x].second = LastRoad();
		to[x][p[x].second] = p[x].first;
	}
	for(int i=1; i<=deg[x]; i++){
		if(to[x][i]==0){
			Move(i, 2);
			int c = Color();
			int t = LastRoad();
			if(c==1){
				N++;
				p[N].first = x;
				gp2[x].pb(N);
				gp2[N].pb(x);
				to[x][i] = N;
				dfs1(N); 
				Move(p[to[x][i]].second, 3);
			}else if(c==2){
				to[x][i] = -1;
				Move(LastRoad(), 2);
			}else{
				to[x][i] = -2;
				Move(LastRoad(), 3);
			}
		}
	}
}

void dfs2(int x){
	//cout<<x<<endl;
	for(int i=1; i<=deg[x]; i++){
		if(to[x][i]==p[x].first)	continue;
		if(to[x][i]==-2)	continue;
		if(to[x][i]==-1){
			Move(i, 1);
			int c = Color();
			if(c==2){
				s[x][i] = (s[x][i]+e[x][i])/2+1;
			}else{
				e[x][i] = (s[x][i]+e[x][i])/2;
			}
			Move(LastRoad(), c);
			if(s[x][i]==e[x][i]){
				gp2[x].pb(s[x][i]);
				gp2[s[x][i]].pb(x);
				to[x][i] = -2;
			}
		}else{
			if(chk[x]){
				Move(i, 3);
				dfs2(to[x][i]);
				Move(p[to[x][i]].second, 1);
			}else{
				Move(i, 2);
				dfs2(to[x][i]);
				Move(p[to[x][i]].second, 1);
			}
		}
	}
}

vector<pii> v1, v2;

int dist[MAX_N+1];
int ans[MAX_N+1];

deque<int> dq;

void bfs(int x){
	dq.pb(x);
	dist[x] = 0;
	while(!dq.empty()){
		int now = dq.front(); dq.pop_front();
		for(int i : gp2[now]){
			if(dist[i]>dist[now]+1){
				dist[i] = dist[now]+1;
				dq.pb(i);
			}
		}
	}
}

void Inspect(int R){
	dfs1(1);
	v1.pb({1, N});
	for(int i=1; i<=N; i++){
		for(int j=1; j<=deg[i]; j++){
			if(to[i][j]==-1){
				s[i][j] = 1;
				e[i][j] = N;
			}
		}
	}
	while(!v1.empty()){
		for(pii p : v1){
			if(p.first!=p.second){
				v2.pb({p.first, (p.first+p.second)/2});
				v2.pb({(p.first+p.second)/2+1, p.second});
			}
		}
		while(!v1.empty())	v1.pop_back();
		for(pii p : v2){
			v1.pb(p);
		}
		while(!v2.empty())	v2.pop_back();
		for(int i=1; i<=N; i++){
			chk[i] = false;
		}
		if(v1.empty())	break;
		for(int i=0; i<v1.size(); i+=2){
			pii p = v1[i];
			for(int j=p.first; j<=p.second; j++){
				chk[j] = true;
			}
		}
		dfs2(1);
	}
	for(int i=1; i<=N; i++){
		for(int j=1; j<=N; j++){
			dist[j] = INF;
		}
		bfs(i);
		//cout<<i<<endl;
		for(int j=1; j<=N; j++){
			//cout<<j<<" "<<dist[j]<<endl;
			if(dist[j]!=0){
				ans[dist[j]]++;
			}
		}
	}
	for(int i=1; i<=R; i++){
		//cout<<i<<" "<<ans[i]<<endl;
		if(i<=N){
			Answer(i, ans[i]/2);
		}else{
			Answer(i, 0);
		}
	}
}

Compilation message (stderr)

dungeon2.cpp: In function 'void dfs1(int)':
dungeon2.cpp:39:8: warning: unused variable 't' [-Wunused-variable]
    int t = LastRoad();
        ^
dungeon2.cpp: In function 'void Inspect(int)':
dungeon2.cpp:140:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<v1.size(); i+=2){
                ~^~~~~~~~~~

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