Submission #126037

#	Time	Username	Problem	Language	Result	Execution time	Memory
126037		tinder	Dungeon 2 (JOI16_dungeon2)	C++14	95 / 100	34 ms	1400 KiB

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;
	}
};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
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;
}

bool allblack(int l, int r) {
	if(l > r) return true;
	return wot[l] and allblack(l + 1, r);
}
bool allwhite(int l, int r) {
	if(l > r) return true;
	return (!wot[l]) and (!allwhite(l + 1, r));
}

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

	vector<int> rand_perm(deg[u]);
	iota(rand_perm.begin(), rand_perm.end(), 1);
	shuffle(rand_perm.begin(), rand_perm.end(), rng);

	for(int i : rand_perm) 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]] ? 1 : 2;
	for(edge &e : back[u]) {
		if(e.l == e.r) continue;
		if(allblack(e.l, min(e.r, lvl[u] - 2))) { // left
			e.r = e.l + e.r >> 1;
		} else if(allwhite(e.l, min(e.r, lvl[u] - 2))) { // right
			e.l = (e.l + e.r >> 1) + 1;
		} else {
			Move(e.id, col);
			if(Color() == 1) { // left
				e.r = e.l + e.r >> 1;
			} else { // right
				e.l = (e.l + e.r >> 1) + 1;
			}
			Move(LastRoad(), Color());
		}
	}
	for(auto x : t[u]) {
		Move(x.second, col);
		dfs(x.first);
	}
	if(u != 1) {
		Move(pe[u], 3);
	}
}

void Inspect(int R) {
	for(int i = 1; i <= 200; i++) {
		for(int j = 1; j <= 200; j++) if(i != j) {
			g[i][j] = inf;
		}
	}

	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) {
		memset(wot, 0, sizeof wot);
		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 m = e.l + e.r >> 1;
					wot[e.l]++, wot[m + 1]--;
					cnt++;
				}
			}
		}
		if(!cnt) break;
		for(int i = 1; i <= mxlvl; i++) {
			wot[i] += wot[i - 1];
		}
		dfs(1);
	}

#ifdef LOCAL_JUDGE
	for(int i = 1; i <= N; i++) {
		cout << i << " ---> ";
		for(int j = 1; j <= N; j++) {
			if(g[i][j] == 1) {
				cout << j << ' ';
			}
		} cout << endl;
	}
#endif

	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 (stderr)

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]
  }
  ^
dungeon2.cpp: In function 'void dfs(int)':
dungeon2.cpp:83:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    e.r = e.l + e.r >> 1;
          ~~~~^~~~~
dungeon2.cpp:85:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    e.l = (e.l + e.r >> 1) + 1;
           ~~~~^~~~~
dungeon2.cpp:89:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     e.r = e.l + e.r >> 1;
           ~~~~^~~~~
dungeon2.cpp:91:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     e.l = (e.l + e.r >> 1) + 1;
            ~~~~^~~~~
dungeon2.cpp: In function 'void Inspect(int)':
dungeon2.cpp:143:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
      int m = e.l + e.r >> 1;
              ~~~~^~~~~

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