oj.uz

Submission #120107

# Submission time Handle Problem Language Result Execution time Memory
120107 2019-06-23T11:18:51 Z tjd229 None (JOI16_dungeon2) C++14
90 / 100
 31 ms 1436 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<pii > 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].first;
			if (v == src) continue;
			if (d[src][v]) continue;
			d[src][v]  = d[src][u] + 1;
			q.push(v);
		}
	}
}
void dfs(int x,int d) {
	int clr = (x / d) % 3;
	
	for (int i = 1; i < edge[x].size(); ++i) {
		//printf("%d,%d/%d : (%d,%d)\n",x,i,edge[x].size(),edge[x][i].first,edge[x][i].second);
		if (i==last[x]) continue;
		if (edge[x][i].second == 3) {
			Move(i, clr + 1);
			int c = Color()-1;
			edge[x][i].first += d * c;
			Move(LastRoad(), c+1);
			continue;
		}
		Move(i,clr+1);
		dfs(edge[x][i].first,d);
	}
	if(x>1)
		Move(last[x], clr+1);
}
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,0 });
	
	Move(++it[N], 2); 
	last[N] = -1; 
	while (stk.size()) {
		if (Color() == 1) {
			edge[++N].resize(NumberOfRoads() + 1, { 0,0 });
			last[N] = LastRoad();
			int p = stk.back();
			edge[N][last[N]] = {p,1};
			edge[p][it[p]] = {N,2};
			stk.push_back(N);
		}
		else if (Color() == 2 && last_op) {
			int top = stk.back();
			edge[top][it[top]] = { 0,3 };//back_edge
			Move(LastRoad(),2);
		}

		int top = stk.back();
		while (it[top]+1 < edge[top].size() 
			&&edge[top][it[top]+1].second!=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 d = 1, i = 0; i < 5; ++i, d *= 3) dfs(1,d);
	/*for (int i = 1; i <= N; ++i) {
		for (auto x : edge[i]) printf("%d,%d ",x.first,x.second);
		puts("");
	}
	return;*/
	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]);
	/*for (reg int i = 1; i <= N; ++i) {
		for (reg int j = i + 1; j <= N; ++j) 
			printf("%d->%d:%d\n",i,j,d[i][j]);
	}*/
	//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 dfs(int, int)':
dungeon2.cpp:30:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < edge[x].size(); ++i) {
                  ~~^~~~~~~~~~~~~~~~
dungeon2.cpp: In function 'void Inspect(int)':
dungeon2.cpp:71:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (it[top]+1 < edge[top].size() 
          ~~~~~~~~~~^~~~~~~~~~~~~~~~~~
dungeon2.cpp:75: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 2 ms 384 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

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 512 KB Output is correct
7 Correct 2 ms 384 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 384 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 512 KB Output is correct

Subtask #3
46.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 Partially correct 5 ms 896 KB Partially correct
4 Partially correct 31 ms 1408 KB Partially correct
5 Partially correct 2 ms 512 KB Partially correct
6 Partially correct 3 ms 640 KB Partially correct
7 Partially correct 3 ms 896 KB Partially correct
8 Partially correct 3 ms 896 KB Partially correct
9 Partially correct 4 ms 896 KB Partially correct
10 Partially correct 3 ms 896 KB Partially correct
11 Partially correct 3 ms 896 KB Partially correct
12 Partially correct 5 ms 896 KB Partially correct
13 Partially correct 7 ms 1024 KB Partially correct
14 Correct 3 ms 896 KB Output is correct
15 Partially correct 4 ms 896 KB Partially correct
16 Partially correct 6 ms 768 KB Partially correct
17 Partially correct 29 ms 1404 KB Partially correct
18 Partially correct 27 ms 1400 KB Partially correct
19 Partially correct 28 ms 1436 KB Partially correct