oj.uz

Submission #27254

# Submission time Handle Problem Language Result Execution time Memory
27254 2017-07-11T15:37:10 Z youaremysky99 None (JOI16_dungeon2) C++14
44 / 100
 29 ms 2908 KB 
#include "dungeon2.h"
#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <cstring>
#include <queue>

using namespace std;

#define For(i,a,b) for (int i = (a), _b = (b); i <= _b; i++)
#define sz(a) ((int)a.size())
typedef pair<int,int> pt;

/// use Anser(int D, int A) for answering 
/// use Move(int I, int V) for moving and leaving stones
/// LastRoad() 
/// NumberOfRoads()
/// Color()

const int maxn = 202;
int n;
map<vector<int>,int> mapNode;
vector<int> from[maxn];
vector<pt> V[maxn]; /// edges 
vector<int> need[maxn];
int maxDep;
int papa[maxn];
bool edge[maxn][maxn];
int level[maxn];

void insertNewNode(vector<int> trace) {
	n++;
	mapNode[trace] = n;
	from[n] = trace;
}

void dfs(vector<int> trace, int u, int dep = 1) {
	maxDep = max(maxDep, dep);
	int D = NumberOfRoads();
	level[u] = dep;
	For(i,1,D) {
		if (sz(trace) && i == trace.back()) continue;
		Move(i, 2);
		if (Color() == 1) {
			int last = LastRoad();
			vector<int> newTrace = trace;
			newTrace.push_back(last); 
			insertNewNode(newTrace);
			V[u].push_back(make_pair(n, i)); edge[u][n] = edge[n][u] = true;
			papa[n] = u;
			dfs(newTrace, n, dep + 1);
		} else {
			if (sz(trace) && Color() == 2) {
				need[u].push_back(i); /// the edge needs to be identify
			}
			int last = LastRoad();
			Move(last, Color());
		}
	}
	if (sz(trace)) Move(trace.back(), 3);
}

int filled[maxn][8];
int maxLay;

void build(int L, int R, int dep) {
	if (L >= R) {
		filled[L][dep] = 1;
		return;
	}
	int block = (R - L + 1) / 3 + 1; 
	For(i,L,min(R,L + block - 1)) {
		filled[i][dep] = 1;
	}
	build(L, min(R,L + block - 1), dep + 1);
	L = min(R, L + block - 1) + 1;

	For(i,L,min(R,L + block - 1)) {
		filled[i][dep] = 2;
	}
	build(L, min(R,L + block - 1), dep + 1);
	L = min(R, L + block - 1) + 1;

	For(i,L,min(R,L + block - 1)) {
		filled[i][dep] = 3;
	}
	build(L, min(R,L + block - 1), dep + 1);
}

void init() {
	maxLay = 5;
	For(lay,1,maxLay) {
		For(i,1,maxDep) filled[i][lay] = 1;
	}
	build(1,maxDep,1);
	
}

vector<int> receive[maxn][11];
void go(int u, int dep, int lay) {
	For(lay,1,maxLay) receive[u][lay].resize(sz(need[u]));
	for (int i = 0; i < (int)need[u].size() ; i++) {
		int id = need[u][i];
		Move(id, Color());
		receive[u][lay][i] = Color();
		Move(LastRoad(), Color());
	}

	for (auto e : V[u]) {
		Move(e.second, filled[dep][lay]);
		go(e.first, dep + 1, lay);
	}

	if (u != 1) {
		Move(from[u].back(), Color());
	}
}

int getDep(vector<int> rec) {
	int cur = 1;
	For(lay,1,maxLay) {
		while (filled[cur][lay] < rec[lay]) ++cur;
	}
	return cur;
}

int totRes[maxn];
int d[maxn];

void bfs(int st) {
	queue<int> qu;
	memset(d,-1,sizeof(d));
	d[st] = 0;
	qu.push(st);

	while (sz(qu)) {
		int u = qu.front(); qu.pop();
		For(v,1,n) if (edge[u][v]) {
			//int v = x.first;
			if (d[v] == -1) {
				d[v] = d[u] + 1;
				qu.push(v);
			}
		}
	}

	For(i,1,n) totRes[d[i]]++;
}

void Inspect(int R) {
	memset(edge,false,sizeof(edge));
	maxDep = 0;
	n = 0;
	insertNewNode(vector<int>(0));
	dfs(vector<int>(0), 1);

	init();
	For(lay,1,maxLay) {
		go(1,1,lay);
	}
	
	For(u,2,n) {
		for (int i = 0; i < need[u].size(); i++) {
			int id = need[u][i];
			vector<int> token; token.push_back(0);
			For(lay,1,maxLay) {
				token.push_back(receive[u][lay][i]);
			}
			int k = getDep(token);
			int p = u;
			while (level[p] > k) p = papa[p];
			edge[p][u] = edge[u][p] = true;
		}
	}

	For(u,1,n) bfs(u);


	For(i,1,R) Answer(i, totRes[i] / 2);
}

Compilation message

dungeon2.cpp: In function 'void Inspect(int)':
dungeon2.cpp:164:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < need[u].size(); i++) {
                     ^
dungeon2.cpp:165:8: warning: unused variable 'id' [-Wunused-variable]
    int id = need[u][i];
        ^

Subtask #1
17.0 / 17.0

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

Subtask #2
27.0 / 27.0

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

Subtask #3
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2776 KB Output is correct
2 Correct 23 ms 2776 KB Output is correct
3 Incorrect 29 ms 2908 KB Wrong Answer [4]
4 Halted 0 ms 0 KB -