Submission #120095

#	Time	Username	Problem	Language	Result	Execution time	Memory
120095		tjd229	Dungeon 2 (JOI16_dungeon2)	C++14	0 / 100	3 ms	896 KiB

dungeon2

#include "dungeon2.h"
#include <vector>
#include <queue>
#define pii pair<int,int>
#define reg register
using namespace std;
int d[201][201];
int it[201];
int last[201];
int N;
vector<int > edge[201]; //ix,forw or rev or back
void bfs(int src) {
	queue<int> q;
	q.push(src);
	while (q.size()) {
		int u = q.front();
		q.pop();
		for (reg int i = 1; i < edge[u].size(); ++i) {
			int v = edge[u][i];
			if (v == src) continue;
			if (d[src][v]) continue;
			d[src][v]=d[v][src] = d[src][u] + 1;
			q.push(v);
		}
	}
}
void Inspect(int R)
{
	bool last_op = 1;//1: stk_push, 0: stk_pop
	vector<int > stk;
	stk.push_back(++N); 
	edge[N].resize(NumberOfRoads()+1,0);
	
	Move(++it[N], 2); 
	last[N] = -1; 
	while (stk.size()) {
		if (Color() == 1) {
			edge[++N].resize(NumberOfRoads()+1,0);
			last[N] = LastRoad();
			int p = stk.back();
			edge[N][last[N]] = p;
			edge[p][it[p]] = N;
			stk.push_back(N);
		}
		else if (Color() == 2 && last_op) {
			vector<int > stk2;
			int ix = LastRoad();
			int v = stk.back();
			Move(LastRoad(),3);
			while (Color() != 3) {
				int top = stk.back();
				stk2.push_back(top); stk.pop_back();
				Move(last[top],2);
			}
			int u = stk.back();
			edge[u][ix] = v;
			edge[v][it[v]] = u;
			Move(it[u],2);
			while (stk2.size()>1) {
				int top = stk2.back();
				stk.push_back(top); stk2.pop_back();
				Move(it[top], 2);
			}
			stk.push_back(stk2[0]);
		}

		int top = stk.back();
		while (it[top]+1 < edge[top].size() 
			&&edge[top][it[top]+1]!=0) { //if -> while
			++it[top];
		}
		if (it[top]+1 < edge[top].size()) {
			Move(++it[top],2);
			last_op = 1;
		}
		else {
			stk.pop_back();
			if(last[top]>0)
				Move(last[top], 2);
			last_op = 0;
		}
	}

	/*for (int i = 1; i <= N; ++i) {
		for (auto x : edge[i]) printf("%d ",x);
		puts("");
	}*/
	
	for (int i = 1; i <= N; ++i) bfs(i);
	int hist[201] = { 0 };
	for (reg int i = 1; i <= N; ++i) {
		for (reg int j = i + 1; j <= N; ++j) ++hist[d[i][j]];
	}
	for (int i = 1; i <= R; ++i) Answer(i,hist[i]);
	//BFS -> dist calc
	//report val calc
	//answer
}

Compilation message (stderr)

dungeon2.cpp: In function 'void bfs(int)':
dungeon2.cpp:18:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (reg int i = 1; i < edge[u].size(); ++i) {
                       ~~^~~~~~~~~~~~~~~~
dungeon2.cpp: In function 'void Inspect(int)':
dungeon2.cpp:68:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (it[top]+1 < edge[top].size() 
          ~~~~~~~~~~^~~~~~~~~~~~~~~~~~
dungeon2.cpp:72:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (it[top]+1 < edge[top].size()) {
       ~~~~~~~~~~^~~~~~~~~~~~~~~~~~

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