Submission #100879

#	Time	Username	Problem	Language	Result	Execution time	Memory
100879		autumn_eel	Dungeon 2 (JOI16_dungeon2)	C++14	44 / 100	32 ms	768 KiB

dungeon2

#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
typedef pair<vector<int>,int>P;

#include "dungeon2.h"

void move(int i,int c){
	Move(i+1,c+1);
}
int lastroad(){
	int res=LastRoad();
	if(res==-1)return -1;
	return res-1;
}
int color(){
	return Color()-1;
}


int cnt[200];

void Inspect(int R){
	vector<vector<int>>vs;
	queue<P>que;
	que.push({});
	move(0,1);
	move(lastroad(),color());
	while(!que.empty()){
		auto v=que.front();que.pop();
		vs.push_back(v.first);
		cnt[v.second]++;
		deque<int>b;
		for(int u:v.first){
			move(u,color());
			b.push_front(lastroad());
		}
		int E=NumberOfRoads();
		rep(i,E){
			move(i,color());
			if(color()!=0){
				move(lastroad(),color());
				continue;
			}
			move(lastroad(),1);
			v.first.push_back(i);
			que.push(P(v.first,v.second+1));
			v.first.pop_back();
		}
		for(int u:b){
			move(u,color());
		}
	}
	for(auto&root:vs){
		if(root.empty())continue;
		for(auto&r:vs){
			deque<int>b;
			for(int u:r){
				move(u,color());
				b.push_front(lastroad());
			}
			move(0,0);
			move(lastroad(),color());
			for(int u:b){
				move(u,color());
			}
		}
		deque<int>b;
		for(int u:root){
			move(u,color());
			b.push_front(lastroad());
		}
		queue<P>que;
		que.push({});
		move(0,1);
		move(lastroad(),color());
		while(!que.empty()){
			auto v=que.front();que.pop();
			cnt[v.second]++;
			deque<int>b;
			for(int u:v.first){
				move(u,color());
				b.push_front(lastroad());
			}
			int E=NumberOfRoads();
			rep(i,E){
				move(i,color());
				if(color()!=0){
					move(lastroad(),color());
					continue;
				}
				move(lastroad(),1);
				v.first.push_back(i);
				que.push(P(v.first,v.second+1));
				v.first.pop_back();
			}
			for(int u:b){
				move(u,color());
			}
		}
		for(int u:b){
			move(u,color());
		}
	}
	for(int i=1;i<=R;i++){
		Answer(i,cnt[i]/2);
	}
}

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