Submission #637287

#	Time	Username	Problem	Language	Result	Execution time	Memory
637287		imeimi2000	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	5997 ms	658388 KiB

dungeons

#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 / 11
• Subtask 2: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 11 / 11