Submission #599453

#	Time	Username	Problem	Language	Result	Execution time	Memory
599453		definitelynotmee	Dungeons Game (IOI21_dungeons)	C++17	11 / 100	7099 ms	893456 KiB

dungeons

#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix= vector<vector<T>>;
const int T = 1;

struct jmp{
	ll to, plus, win;
	jmp merge(jmp b){
		jmp ret;
		ret.to = b.to;
		ret.plus = plus+b.plus;
		ret.win = min(win,b.win-plus);
		return ret;
	}
};

vector<matrix<jmp>> lift;
vector<ll> windp;
int N;
vector<int> S, P, W, L;

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
	N = n;
	S =s;
	P = p;
	W = w;
	L = l;

	int t = T;
	for(int x = 0; x < 13; x++){
		lift.push_back({});
		lift[x] = matrix<jmp>(int(log2(t)+1),vector<jmp>(n));
		for(int i = 0; i < n; i++){
			if(s[i] <= t){
				lift[x][0][i] = {w[i],s[i],1ll<<60};
				if(w[i] == n){
					lift[x][0][i].win = 0, lift[x][0][i].to = i;
				}
			} else {lift[x][0][i] = {l[i],p[i],s[i]};
				if(l[i] == n)
					lift[x][0][i].win = 0, lift[x][0][i].to = i;
			}
		}
		for(int i = 1; i < lift[x].size(); i++){
			for(int j = 0; j < n; j++)
				lift[x][i][j] = lift[x][i-1][j].merge(lift[x][i-1][lift[x][i-1][j].to]);
		}
		t*=2;
	}

	windp = vector<ll>(n+1);
	for(int i = n-1; i >= 0; i--)
		windp[i] = windp[w[i]]+s[i];

	return;
}

long long simulate(int x, int Z) {

	ll z = Z;
	int it = T;

	while(it-- && x != N){
		if(S[x] <= z){
			z+=S[x];
			x=W[x];
		} else {
			z+=P[x];
			x=L[x];
		}
	}
	int power = 0;
	while(x!=N && z < int(1e7)){
		while(z >= T*(1<<power+1))
			power++;
		for(int i = int(lift[power].size())-1; i>= 0; i--){
			if(lift[power][i][x].win > z){
				z+=lift[power][i][x].plus;
				x = lift[power][i][x].to;
			}
		}
		if(S[x] <= z){
			z+=S[x];
			x=W[x];
		} else {
			z+=P[x];
			x=L[x];
		}
	}

	return z+windp[x];
}

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<jmp, std::allocator<jmp> >, std::allocator<std::vector<jmp, std::allocator<jmp> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int i = 1; i < lift[x].size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:82:25: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   82 |   while(z >= T*(1<<power+1))
      |                    ~~~~~^~

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