oj.uz

답안 #637287

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
637287 2022-09-01T09:32:14 Z imeimi2000 던전 (IOI21_dungeons) C++17
100 / 100
 5997 ms 658388 KB 
#include "dungeons.h"
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>

using namespace std;
using ll = long long;

const int L = 24;
int n;
vector<int> last, win;
vector<int> E[400005];
bool vis[400005];
int sz[400005], cnt;
int bound[400005];
struct hld {
	int nxt[400005];
	int lose[400005];
	int par[400005];
	void dfs_sz(int x) {
		sz[x] = 1;
		for (int i : E[x]) {
			if (sz[i]) continue;
			par[i] = x;
			dfs_sz(i);
			sz[x] += sz[i];
		}
	}
	int hld_chain[400005];
	int dfs_ord[400005];
	int vertex[400005];
	int hpath_bound[400005];
	int prefix_bound[400005];
	ll seg[1 << 20], dep[400005];
	void dfs_hld(int x) {
		vertex[dfs_ord[x] = cnt++] = x;
		hpath_bound[x] = min(hpath_bound[x], bound[x]);
		prefix_bound[x] = min(prefix_bound[x], bound[x]);
		for (auto it = E[x].begin(); it != E[x].end(); ++it) if (sz[*it] >= sz[x]) {
			E[x].erase(it);
			break;
		}
		for (int &i : E[x]) {
			if (sz[E[x][0]] < sz[i]) swap(E[x][0], i);
		}
		for (int i : E[x]) {
			dep[i] = dep[x] + lose[i];
			if (i == E[x][0]) {
				hld_chain[i] = hld_chain[x];
				hpath_bound[i] = max(0, hpath_bound[x] - lose[i]);
			}
			else {
				hld_chain[i] = i;
			}
			prefix_bound[i] = max(0, prefix_bound[x] - lose[i]);
			dfs_hld(i);
		}
	}
	void init(int i, int s, int e) {
		if (s == e) {
			int v = vertex[s];
			seg[i] = bound[v] + dep[v];
			return;
		}
		int m = (s + e) / 2;
		init(i + i, s, m);
		init(i + i + 1, m + 1, e);
		seg[i] = min(seg[i + i], seg[i + i + 1]);
	}
	void init() {
		for (int i = 0; i <= n; ++i) E[i].clear();
		memset(vis, 0, sizeof(vis));
		memset(sz, 0, sizeof(sz));
		memset(par, -1, sizeof(par));
		memset(hpath_bound, 0x3f, sizeof(hpath_bound));
		memset(prefix_bound, 0x3f, sizeof(prefix_bound));
		for (int i = 0; i <= n; ++i) {
			E[nxt[i]].push_back(i);
		}
		cnt = 0;
		for (int i = 0; i <= n; ++i) {
			if (sz[i]) continue;
			int x = i;
			while (!vis[x]) {
				vis[x] = true;
				x = nxt[x];
			}
			dfs_sz(x);
			hld_chain[x] = x;
			dep[x] = 0;
			dfs_hld(x);
		}
		init(1, 0, n);
	}
	int find(int i, int s, int e, int y, ll v) const {
		if (seg[i] > v || y < s) return -1;
		if (s == e) return vertex[s];
		int m = (s + e) / 2;
		int r = find(i + i + 1, m + 1, e, y, v);
		if (r != -1) return r;
		return find(i + i, s, m, y, v);
	}
	void simulate_once(int &x, int &z) const {
		int v = find(1, 0, n, dfs_ord[x], z + dep[x]);
		// printf("[%d, %lld]\n", v, z + dep[x] - dep[v]);
		z += dep[x] - dep[v] + win[v];
		x = last[v];
	}
	void simulate(int &x, int &z) const {
		// for (int i = 0; i <= n; ++i) printf("nxt[%d] = %d, lose[%d] = %d, bound[%d] = %d\n", i, nxt[i], i, lose[i], i, bound[i]);
		// printf("[%d, %d] -> ", x, z);
		while (true) {
			if (hpath_bound[x] <= z) {
				simulate_once(x, z);
				return;
			}
			int p = par[hld_chain[x]];
			if (p == -1) {
				z += dep[x];
				x = hld_chain[x];
				break;
			}
			z += dep[x] - dep[p];
			x = p;
			// printf("[%d, %d] -> ", x, z);
		}
		int rt = lose[x];
		z += rt;
		x = nxt[x];
		// printf("[%d, %d] -> ", x, z);
		if (prefix_bound[x] > z) {
			int add = dep[x] + rt;
			z += ((prefix_bound[x] - z - 1) / add + 1) * add;
			// printf("[%d, %d] -> ", x, z);
		}
		while (true) {
			if (hpath_bound[x] <= z) {
				simulate_once(x, z);
				return;
			}
			int p = par[hld_chain[x]];
			if (p == -1) exit(1);
			z += dep[x] - dep[p];
			x = p;
			// printf("[%d, %d] -> ", x, z);
		}
		exit(2);
	}
} sub[L];

ll win_all[400005];
const int inf = 1e8;

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
	::n = n;
	::win = s;
	::win.push_back(0);
	::last = w;
	::last.push_back(n);
	win_all[n] = 0;
	for (int i = n; i--; ) win_all[i] = win_all[w[i]] + s[i];
	for (int i = 0; i < L; ++i) {
		int d = 1 << i;
		for (int j = 0; j < n; ++j) {
			if (s[j] <= d) {
				sub[i].nxt[j] = w[j];
				sub[i].lose[j] = s[j];
				bound[j] = inf;
			}
			else {
				sub[i].nxt[j] = l[j];
				sub[i].lose[j] = p[j];
				bound[j] = s[j];
			}
			sub[i].nxt[n] = n;
			sub[i].lose[n] = 0;
			bound[n] = 0;
		}
		sub[i].init();
	}
	return;
}

long long simulate(int x, int z) {
	for (int i = 0; i < L; ++i) if (x < n && (1 << i) <= z && z < (1 << (i + 1))) sub[i].simulate(x, z);
	return z + win_all[x];
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 125516 KB Output is correct
2 Correct 52 ms 125520 KB Output is correct
3 Correct 56 ms 127856 KB Output is correct
4 Correct 238 ms 188048 KB Output is correct
5 Correct 56 ms 127880 KB Output is correct
6 Correct 229 ms 187884 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 126724 KB Output is correct
2 Correct 2156 ms 644508 KB Output is correct
3 Correct 2095 ms 656692 KB Output is correct
4 Correct 2598 ms 658228 KB Output is correct
5 Correct 3801 ms 625020 KB Output is correct
6 Correct 2171 ms 643548 KB Output is correct
7 Correct 963 ms 655552 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 126684 KB Output is correct
2 Correct 270 ms 189392 KB Output is correct
3 Correct 262 ms 192276 KB Output is correct
4 Correct 198 ms 193040 KB Output is correct
5 Correct 213 ms 191392 KB Output is correct
6 Correct 308 ms 189008 KB Output is correct
7 Correct 329 ms 189048 KB Output is correct
8 Correct 239 ms 192876 KB Output is correct
9 Correct 326 ms 188716 KB Output is correct
10 Correct 238 ms 192684 KB Output is correct
11 Correct 408 ms 193016 KB Output is correct
12 Correct 427 ms 193152 KB Output is correct
13 Correct 222 ms 193068 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 126684 KB Output is correct
2 Correct 270 ms 189392 KB Output is correct
3 Correct 262 ms 192276 KB Output is correct
4 Correct 198 ms 193040 KB Output is correct
5 Correct 213 ms 191392 KB Output is correct
6 Correct 308 ms 189008 KB Output is correct
7 Correct 329 ms 189048 KB Output is correct
8 Correct 239 ms 192876 KB Output is correct
9 Correct 326 ms 188716 KB Output is correct
10 Correct 238 ms 192684 KB Output is correct
11 Correct 408 ms 193016 KB Output is correct
12 Correct 427 ms 193152 KB Output is correct
13 Correct 222 ms 193068 KB Output is correct
14 Correct 61 ms 126664 KB Output is correct
15 Correct 338 ms 189352 KB Output is correct
16 Correct 344 ms 189384 KB Output is correct
17 Correct 249 ms 190804 KB Output is correct
18 Correct 244 ms 190960 KB Output is correct
19 Correct 335 ms 188960 KB Output is correct
20 Correct 265 ms 191332 KB Output is correct
21 Correct 260 ms 191476 KB Output is correct
22 Correct 217 ms 191464 KB Output is correct
23 Correct 341 ms 192336 KB Output is correct
24 Correct 341 ms 193068 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 126684 KB Output is correct
2 Correct 270 ms 189392 KB Output is correct
3 Correct 262 ms 192276 KB Output is correct
4 Correct 198 ms 193040 KB Output is correct
5 Correct 213 ms 191392 KB Output is correct
6 Correct 308 ms 189008 KB Output is correct
7 Correct 329 ms 189048 KB Output is correct
8 Correct 239 ms 192876 KB Output is correct
9 Correct 326 ms 188716 KB Output is correct
10 Correct 238 ms 192684 KB Output is correct
11 Correct 408 ms 193016 KB Output is correct
12 Correct 427 ms 193152 KB Output is correct
13 Correct 222 ms 193068 KB Output is correct
14 Correct 61 ms 126664 KB Output is correct
15 Correct 338 ms 189352 KB Output is correct
16 Correct 344 ms 189384 KB Output is correct
17 Correct 249 ms 190804 KB Output is correct
18 Correct 244 ms 190960 KB Output is correct
19 Correct 335 ms 188960 KB Output is correct
20 Correct 265 ms 191332 KB Output is correct
21 Correct 260 ms 191476 KB Output is correct
22 Correct 217 ms 191464 KB Output is correct
23 Correct 341 ms 192336 KB Output is correct
24 Correct 341 ms 193068 KB Output is correct
25 Correct 261 ms 188324 KB Output is correct
26 Correct 343 ms 189388 KB Output is correct
27 Correct 304 ms 188748 KB Output is correct
28 Correct 296 ms 188876 KB Output is correct
29 Correct 335 ms 189220 KB Output is correct
30 Correct 257 ms 193100 KB Output is correct
31 Correct 316 ms 192840 KB Output is correct
32 Correct 392 ms 192928 KB Output is correct
33 Correct 368 ms 192692 KB Output is correct
34 Correct 533 ms 189192 KB Output is correct
35 Correct 368 ms 192984 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 126724 KB Output is correct
2 Correct 2156 ms 644508 KB Output is correct
3 Correct 2095 ms 656692 KB Output is correct
4 Correct 2598 ms 658228 KB Output is correct
5 Correct 3801 ms 625020 KB Output is correct
6 Correct 2171 ms 643548 KB Output is correct
7 Correct 963 ms 655552 KB Output is correct
8 Correct 52 ms 126684 KB Output is correct
9 Correct 270 ms 189392 KB Output is correct
10 Correct 262 ms 192276 KB Output is correct
11 Correct 198 ms 193040 KB Output is correct
12 Correct 213 ms 191392 KB Output is correct
13 Correct 308 ms 189008 KB Output is correct
14 Correct 329 ms 189048 KB Output is correct
15 Correct 239 ms 192876 KB Output is correct
16 Correct 326 ms 188716 KB Output is correct
17 Correct 238 ms 192684 KB Output is correct
18 Correct 408 ms 193016 KB Output is correct
19 Correct 427 ms 193152 KB Output is correct
20 Correct 222 ms 193068 KB Output is correct
21 Correct 61 ms 126664 KB Output is correct
22 Correct 338 ms 189352 KB Output is correct
23 Correct 344 ms 189384 KB Output is correct
24 Correct 249 ms 190804 KB Output is correct
25 Correct 244 ms 190960 KB Output is correct
26 Correct 335 ms 188960 KB Output is correct
27 Correct 265 ms 191332 KB Output is correct
28 Correct 260 ms 191476 KB Output is correct
29 Correct 217 ms 191464 KB Output is correct
30 Correct 341 ms 192336 KB Output is correct
31 Correct 341 ms 193068 KB Output is correct
32 Correct 261 ms 188324 KB Output is correct
33 Correct 343 ms 189388 KB Output is correct
34 Correct 304 ms 188748 KB Output is correct
35 Correct 296 ms 188876 KB Output is correct
36 Correct 335 ms 189220 KB Output is correct
37 Correct 257 ms 193100 KB Output is correct
38 Correct 316 ms 192840 KB Output is correct
39 Correct 392 ms 192928 KB Output is correct
40 Correct 368 ms 192692 KB Output is correct
41 Correct 533 ms 189192 KB Output is correct
42 Correct 368 ms 192984 KB Output is correct
43 Correct 56 ms 125524 KB Output is correct
44 Correct 59 ms 126864 KB Output is correct
45 Correct 4603 ms 628000 KB Output is correct
46 Correct 3963 ms 623440 KB Output is correct
47 Correct 3908 ms 623868 KB Output is correct
48 Correct 3695 ms 625196 KB Output is correct
49 Correct 4636 ms 628072 KB Output is correct
50 Correct 2166 ms 645832 KB Output is correct
51 Correct 3700 ms 621628 KB Output is correct
52 Correct 2413 ms 644780 KB Output is correct
53 Correct 5511 ms 657412 KB Output is correct
54 Correct 2376 ms 641840 KB Output is correct
55 Correct 2021 ms 627696 KB Output is correct
56 Correct 5502 ms 658132 KB Output is correct
57 Correct 5810 ms 658316 KB Output is correct
58 Correct 5803 ms 658288 KB Output is correct
59 Correct 5997 ms 658388 KB Output is correct
60 Correct 5895 ms 637148 KB Output is correct
61 Correct 5821 ms 650776 KB Output is correct