Submission #621089

#	Time	Username	Problem	Language	Result	Execution time	Memory
621089		amunduzbaev	Dungeons Game (IOI21_dungeons)	C++17	13 / 100	129 ms	36488 KiB

dungeons

#include "dungeons.h"
#ifndef EVAL
#include "grader.cpp"
#endif

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

typedef long long ll;
const int N = 4e5 + 5;
const int M = 25;
vector<int> edges[N];
ll s[N], p[N], w[N], l[N], n;
ll pref[N], par[N][M], sum[N][M];

void dfs(int u){
	//~ for(int j=1;j<20;j++){
		//~ par[u][j] = par[par[u][j-1]][j-1];
		//~ mx[u][j] = max(mx[u][j-1], mx[par[u][j-1]][j-1]);
	//~ }
	
	for(auto x : edges[u]){
		pref[x] = pref[u] + s[x];
		//~ par[x][0] = u, mx[x][0] = s[u] + pref[u];
		dfs(x);
	}
}

void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L) {
	n = N;
	for(int i=0;i<n;i++){
		s[i] = S[i], p[i] = P[i], w[i] = W[i], l[i] = L[i];
		edges[w[i]].push_back(i);
		par[i][0] = l[i];
		sum[i][0] = p[i];
	}
	l[n] = n, par[n][0] = n;
	
	//~ par[n][0] = n;
	dfs(n);
	for(int j=1;j<M;j++){
		for(int i=0;i<=n;i++){
			par[i][j] = par[par[i][j-1]][j-1];
			sum[i][j] = sum[i][j-1] + sum[par[i][j-1]][j-1];
		}
	}
}

//~ ll go(int x, ll z){
	//~ cout<<x<<" "<<z<<"\n";
	//~ if(s[x] > z){
		//~ return go(l[x], z + s[x]);
	//~ }
	
	//~ z += pref[x];
	//~ for(int j=19;~j;j--){
		//~ if(mx[x][j] <= z){
			//~ x = par[x][j];
		//~ }
	//~ }
	
	//~ x = par[x][0];
	//~ if(x == n) return z;
	//~ z -= pref[x];
	//~ return go(l[x], z + s[x]);
//~ }

ll simulate(int x, int z) {
	ll res = z;
	for(int j=M-1;~j;j--){
		if(res + sum[x][j] < s[0]){
			res += sum[x][j];
			x = par[x][j];
		}
	}
	
	if(res >= s[0]){
		return res + pref[x];
	}
	res += p[x];
	x = l[x];
	res += pref[x];
	return res;
}

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