oj.uz

Submission #120098

# Submission time Handle Problem Language Result Execution time Memory
120098 2019-06-23T10:41:36 Z tjd229 None (JOI16_dungeon2) C++14
44 / 100
 6 ms 896 KB 
#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[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

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
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 2 ms 512 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 2 ms 512 KB Output is correct
14 Correct 2 ms 512 KB Output is correct
15 Correct 2 ms 384 KB Output is correct

Subtask #3
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 896 KB Output is correct
2 Partially correct 3 ms 896 KB Partially correct
3 Incorrect 6 ms 896 KB Output isn't correct
4 Halted 0 ms 0 KB -