Submission #1196945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196945		belgianbot	Dungeons Game (IOI21_dungeons)	C++20	13 / 100	1423 ms	62880 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

const int LOG = 20;
vector<vector<long long>> distW, nxtW, miniW, distL, nxtL, miniL;
vector<long long> distparent;
vector<int> parent;
vector<int> s,p,w,l;
int n;

pair<int,long long> getparent(int x) {
	if (parent[x] == x) return {x,0};
	pair<int, long long> res = getparent(parent[x]);
	parent[x] = res.first;
	distparent[x] += res.second;
	return (make_pair(parent[x], distparent[x]));
}

void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	s = ss; p = pp; w = ww; l = ll; n = nn;
	l.push_back(n); p.push_back(0); s.push_back(0); w.push_back(n);
	

	distW.resize(n+1, vector<long long>(LOG));
	nxtW.resize(n+1, vector<long long>(LOG));
	miniW.resize(n+1, vector<long long>(LOG));
	distL.resize(n+1, vector<long long>(LOG));
	nxtL.resize(n+1, vector<long long>(LOG));
	miniL.resize(n+1, vector<long long>(LOG));
	distparent.resize(n+1);
	parent.resize(n+1);

	for (int j = 0; j <= n; j++) {
		parent[j] = j;
		distparent[j] = 0;
		distW[j][0] = s[j];
		nxtW[j][0] = w[j];
		miniW[j][0] = s[w[j]] - s[j];
		distL[j][0] = p[j];
		nxtL[j][0] = l[j];
		miniL[j][0] = s[l[j]] - p[j];
	}
	
	for (int k = 1; k < LOG; k++){
			for (int j = 0; j <= n; j++) {
			distW[j][k] = distW[j][k-1] + distW[nxtW[j][k-1]][k-1];
			nxtW[j][k] = nxtW[nxtW[j][k-1]][k-1];
			miniW[j][k] = max(miniW[j][k-1], miniW[nxtW[j][k-1]][k-1] - distW[j][k-1]);
			distL[j][k] = distL[j][k-1] + distL[nxtL[j][k-1]][k-1];
			nxtL[j][k] = nxtL[nxtL[j][k-1]][k-1];
			miniL[j][k] = min(miniL[j][k-1], miniL[nxtL[j][k-1]][k-1] - distL[j][k-1]);
		}
	}
}

long long simulate(int x, int z) {
	long long st = z;
	int pos = x;
	
	while (pos != n) {
		if (st < s[pos]) {
			for (int i = LOG-1; i >= 0; i--) {
				if (st >= miniL[pos][i]) continue;
				st += distL[pos][i];
				pos = nxtL[pos][i];
			}
			st += p[pos];
			pos = l[pos];
		}
		else {
			pair<int, long long> res = getparent(pos);
			st += res.second; pos = res.first;
			for (int i = LOG-1; i >= 0; i--) {
				if (st < miniW[pos][i]) continue;
				pair<int, long long> res2 = getparent(nxtW[pos][i]);
				distparent[pos] = distW[pos][i] + res2.second;
				parent[pos] = res2.first;
				st += distW[pos][i] + res2.second;
				pos = res2.first;
			}
			st += s[pos];
			pos = w[pos];
		}
	}
	return st;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 26
• Subtask 3: 13 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11