Submission #100550

#	Time	Username	Problem	Language	Result	Execution time	Memory
100550		Pro_ktmr	Dungeon 2 (JOI16_dungeon2)	C++14	0 / 100	17 ms	768 KiB

dungeon2

#include<bits/stdc++.h>
using namespace std;
#define MP(a,b) make_pair(a,b)

#include"dungeon2.h"

//void Answer(int D, int A)
//void Move(int I, int C)
//int NumberOfRoads()
//int LastRoad()
//int Color()

struct way{
public:
	vector<int> toGo;
	vector<int> toRe;
};

int ans[201] = {};
void wfs(int c){
	queue<pair<way,int> > que;
	way w;
	que.push(MP(w,0));
	while(!que.empty()){
		w = que.front().first;
		int cost = que.front().second;
		ans[cost]++;
		que.pop();
		for(int i=0; i<w.toGo.size(); i++){
			Move(w.toGo[i], c);
		}
		for(int i=0; i<NumberOfRoads(); i++){
			if(w.toRe.size() > 0 && w.toRe.back() == i+1) continue;
			Move(i+1, c);
			if(Color() != c){
				w.toGo.push_back(i+1);
				w.toRe.push_back(LastRoad());
				que.push(MP(w,cost+1));
				w.toGo.pop_back();
				w.toRe.pop_back();
			}
			Move(LastRoad(), c);
		}
		for(int i=w.toRe.size()-1; i>=0; i--){
			Move(w.toRe[i], c);
		}
	}
}

void Inspect(int R){
	queue<way> que;
	vector<way> ways;
	way w;
	que.push(w);
	ways.push_back(w);
	while(!que.empty()){
		w = que.front();
		que.pop();
		for(int i=0; i<w.toGo.size(); i++){
			Move(w.toGo[i], 2);
		}
		for(int i=0; i<NumberOfRoads(); i++){
			if(w.toRe.size() > 0 && w.toRe.back() == i+1) continue;
			Move(i+1, 2);
			if(Color() == 1){
				w.toGo.push_back(i+1);
				w.toRe.push_back(LastRoad());
				que.push(w);
				ways.push_back(w);
				w.toGo.pop_back();
				w.toRe.pop_back();
			}
			Move(LastRoad(), 2);
		}
		for(int i=w.toRe.size()-1; i>=0; i--){
			Move(w.toRe[i], 2);
		}
	}
	
	int now = 2;
	for(int i=0; i<ways.size(); i++){
		for(int i=0; i<w.toGo.size(); i++){
			Move(w.toGo[i], now);
		}
		if(now == 2) now = 1;
		else now = 2;
		wfs(now);
		for(int i=w.toRe.size()-1; i>=0; i--){
			Move(w.toRe[i], now);
		}
	}
	for(int i=1; i<=R; i++){
		Answer(i, ans[i]/2);
		//cout << ans[i] << endl;
	}
}

Compilation message (stderr)

dungeon2.cpp: In function 'void wfs(int)':
dungeon2.cpp:29:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<w.toGo.size(); i++){
                ~^~~~~~~~~~~~~~
dungeon2.cpp: In function 'void Inspect(int)':
dungeon2.cpp:59:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<w.toGo.size(); i++){
                ~^~~~~~~~~~~~~~
dungeon2.cpp:81:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ways.size(); i++){
               ~^~~~~~~~~~~~
dungeon2.cpp:82:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<w.toGo.size(); i++){
                ~^~~~~~~~~~~~~~

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