Submission #126046

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
126046	2019-07-06T21:01:40 Z	tinder	None (JOI16_dungeon2)	C++14	100 / 100	31 ms	1276 KB

dungeon2

#include "dungeon2.h"
#include <bits/stdc++.h>
using namespace std;

struct edge {
	int id, l, r;
	edge() {}
	edge(int id, int l, int r) {
		this -> id = id, this -> l = l, this -> r = r;
	}
	bool operator < (const edge &o) const {
		id < o.id;
	}
};

const int maxn = 2e2 + 5;
const int inf = 1e5;

int deg[maxn], pe[maxn];
int dad[maxn], lvl[maxn];
int N, M;
int ptr = 0;
map<int, int> t[maxn];
vector<edge> back[maxn];
int wot[maxn];
int g[maxn][maxn];

int AncAtLvl(int u, int l) {
	assert(lvl[u] > l);
	while(lvl[u] != l) {
		u = dad[u];
	} return u;
}

void add_edge(int u, int v) {
	g[u][v] = g[v][u] = 1;
}

void discover(int u, int par) {
	pe[u] = LastRoad();
	dad[u] = par;
	deg[u] = NumberOfRoads();
	lvl[u] = u == 1 ? 0 : lvl[par] + 1;

	for(int i = 1; i <= deg[u]; i++) if(i != pe[u]) {
		Move(i, 2);
		if(Color() == 1) {
			int v = ++ptr;
			add_edge(u, v);
			t[u][v] = i;
			discover(v, u);
		} else {
			if(Color() == 2) {
				back[u].emplace_back(i, 69, 69);
			}
			Move(LastRoad(), Color());
		}
	}
	if(u != 1) {
		Move(pe[u], 3);
	}
}

void dfs(int u) {
	int col = wot[lvl[u]] ? wot[lvl[u]] : 1;
	for(edge &e : back[u]) {
		if(e.l == e.r) continue;
		Move(e.id, col);
		int d = (e.r - e.l) / 3 + 1;
		int m1 = e.l + d, m2 = e.l + d + d;
		if(Color() == 1) { // left
			e.r = m1 - 1;
		} else if(Color() == 2) { // mid
			e.l = m1, e.r = m2 - 1;
		} else { // right
			e.l = m2;
		}
		Move(LastRoad(), Color());
	}
	for(auto x : t[u]) {
		Move(x.second, col);
		dfs(x.first);
	}
	if(u != 1) {
		Move(pe[u], Color());
	}
}

void Inspect(int R) {
	memset(g, 1, sizeof g);
	discover(++ptr, -1);

	N = ptr;
	for(int i = 1; i <= N; i++) {
		M += deg[i];
	}
	M >>= 1;

	int mxlvl = 0;
	for(int i = 1; i <= N; i++) {
		mxlvl = max(mxlvl, lvl[i]);
	}

	if(mxlvl == 1) { // predictable graph
		goto solution;
	}

	for(int i = 1; i <= N; i++) {
		for(edge &e : back[i]) {
			e.l = 0, e.r = mxlvl - 2;
		}
	}

	while(true) {
		int cnt = 0;
		for(int i = 1; i <= N; i++) {
			for(edge &e : back[i]) {
				if(e.l == e.r) {
					add_edge(i, AncAtLvl(i, e.l));
				} else {
					int d = (e.r - e.l) / 3 + 1;
					int m1 = e.l + d, m2 = e.l + d + d;
					for(int j = e.l; j < m1; j++) {
						wot[j] = 1;
					}
					for(int j = m1; j < m2; j++) {
						wot[j] = 2;
					}
					for(int j = m2; j <= e.r; j++) {
						wot[j] = 3;
					}
					cnt++;
				}
			}
		}
		if(!cnt) break;
		dfs(1);
	}

	solution : ;

	for(int k = 1; k <= N; k++) {
		for(int i = 1; i <= N; i++) {
			for(int j = 1; j <= N; j++) {
				g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
			}
		}
	}

	int ans[maxn];
	memset(ans, 0, sizeof ans);
	for(int i = 1; i <= N; i++) {
		for(int j = i + 1; j <= N; j++) {
			ans[g[i][j]]++;
		}
	}

	for(int i = 1; i <= R; i++) {
		Answer(i, ans[i]);
	}
}

Compilation message

dungeon2.cpp: In member function 'bool edge::operator<(const edge&) const':
dungeon2.cpp:12:6: warning: statement has no effect [-Wunused-value]
   id < o.id;
   ~~~^~~~~~
dungeon2.cpp:13:2: warning: no return statement in function returning non-void [-Wreturn-type]
  }
  ^

Subtask #1

17.0 / 17.0

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

Subtask #2

27.0 / 27.0

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

Subtask #3

56.0 / 56.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	888 KB	Output is correct
2	Correct	12 ms	888 KB	Output is correct
3	Correct	12 ms	988 KB	Output is correct
4	Correct	31 ms	1272 KB	Output is correct
5	Correct	3 ms	632 KB	Output is correct
6	Correct	5 ms	760 KB	Output is correct
7	Correct	12 ms	892 KB	Output is correct
8	Correct	12 ms	888 KB	Output is correct
9	Correct	12 ms	888 KB	Output is correct
10	Correct	12 ms	888 KB	Output is correct
11	Correct	12 ms	888 KB	Output is correct
12	Correct	12 ms	964 KB	Output is correct
13	Correct	15 ms	1116 KB	Output is correct
14	Correct	12 ms	888 KB	Output is correct
15	Correct	12 ms	888 KB	Output is correct
16	Correct	7 ms	760 KB	Output is correct
17	Correct	30 ms	1272 KB	Output is correct
18	Correct	29 ms	1276 KB	Output is correct
19	Correct	29 ms	1272 KB	Output is correct