oj.uz

답안 #126046

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
126046 2019-07-06T21:01:40 Z tinder Dungeon 2 (JOI16_dungeon2) C++14
100 / 100
 31 ms 1276 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;
	}
};

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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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