Submission #834260

#	Time	Username	Problem	Language	Result	Execution time	Memory
834260		Abrar_Al_Samit	Dungeons Game (IOI21_dungeons)	C++17	26 / 100	477 ms	145628 KiB

dungeons

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

const int nax = 4e5 + 3;
int n;
vector<int>s, p, w, l;
int nxtBig[nax];
long long sum_toNext[nax], sum_toN[nax];

vector<int>g[nax];

set<pair<int,int>> dfs(int v, long long sum = 0) {
	if(v < n) sum += s[v];
	sum_toN[v] = sum;

	set<pair<int,int>>me;
	for(int u : g[v]) {
		auto he = dfs(u, sum);
		if(me.size()<he.size()) me.swap(he);
		for(auto e : he) me.insert(e);
	}
	
	while(!me.empty()) {
		auto [val, he] = *me.begin();
		if(v < n && val >= s[v]) break;

		nxtBig[he] = v;
		sum_toNext[he] = sum_toN[he] - sum_toN[v];

		me.erase(me.begin());
	}
	if(v < n) me.insert({s[v], v});
	return me;
}
void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L) {
	n = N, s = S, p = P, w = W, l = L;

	for(int i=0; i<n; ++i) {
		nxtBig[i] = -1;
	}
	for(int i=0; i<n; ++i) {
		g[w[i]].push_back(i);
	}
	dfs(n);
}

const int anax = 1e7;
long long simulate(int x, int z) {

	long long cz = z;
	while(x < n && cz < anax) {
		if(cz >= s[x]) {
			cz += sum_toNext[x];
			x = nxtBig[x];
		} else {
			cz += s[x];
			x = l[x];			
		}
	}
	cz += sum_toN[x];
	return cz;
}

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