Submission #1195838

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195838		Nonoze	Dungeons Game (IOI21_dungeons)	C++20	13 / 100	101 ms	30024 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fi first
#define se second

const int LOG=30;

vector<int> s, p, w, l, dist;
vector<vector<pair<int, int>>> up;
int n;


void init(signed _n, vector<signed> _s, vector<signed> _p, vector<signed> _w, vector<signed> _l) {
	n=_n;
	for (auto &u: _s) s.pb(u);
	for (auto &u: _p) p.pb(u);
	for (auto &u: _w) w.pb(u);
	for (auto &u: _l) l.pb(u);
	dist.resize(n+1); dist[n]=0;
	for (int i=n-1; i>=0; i--) dist[i]=dist[w[i]]+1;
	up.resize(n+1, vector<pair<int, int>>(LOG, {n, 0}));
	for (int i=0; i<n; i++) up[i][0]={l[i], p[i]};
	for (int bit=1; bit<LOG; bit++) {
		for (int i=0; i<n; i++) {
			up[i][bit]=up[up[i][bit-1].fi][bit-1];
			up[i][bit].se+=up[i][bit-1].se;
		}
	}
	return;
}


int simulate(signed x, signed z) {
	int ans=z;
	for (int bit=LOG-1; bit>=0; bit--) {
		if (up[x][bit].fi!=n && up[x][bit].se+ans<s[0]) ans+=up[x][bit].se, x=up[x][bit].fi;
	}
	if (ans<s[0]) ans+=p[x], x=up[x][0].fi;
	return ans+dist[x]*s[0];
}

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