oj.uz

Submission #126043

# Submission time Handle Problem Language Result Execution time Memory
126043 2019-07-06T20:46:19 Z tinder None (JOI16_dungeon2) C++14
0 / 100
 12 ms 1656 KB 
#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;
}

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);
		if(Color() == 1) { // left
			e.r = e.l + (e.r - e.l) / 3;
		} else if(Color() == 2) { // mid
			e.l = e.l + (e.r - e.l) / 3 + 1;
			e.r = e.l + (e.r - e.l) / 3 + (e.r - e.l) / 3 + 1;
		} else { // right
			e.l = e.l + (e.r - e.l) / 3 + (e.r - e.l) / 3 + 2;
		}
		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) {
	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) {
		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);
	}

#ifdef MYPC
	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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 648 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 Runtime error 3 ms 1016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 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 Runtime error 3 ms 1144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #3
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 888 KB Output is correct
2 Runtime error 4 ms 1656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -