Submission #1082382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082382		HappyCapybara	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	7088 ms	883128 KiB

dungeons

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

#define ll long long

int n;
vector<int> s, p, w, l, ds;
vector<vector<vector<ll>>> v;

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;
    s.push_back(0);
    p.push_back(0);
    w.push_back(n);
    l.push_back(n);
	v.resize(n+1, vector<vector<ll>>(30));
	for (int i=0; i<30; i++){
		for (int j=0; j<=n; j++){
			if (i == 0) v[j][i] = {w[j], s[j], s[j]};
			else {
				v[j][i].push_back(v[v[j][i-1][0]][i-1][0]);
				v[j][i].push_back(v[j][i-1][1] + v[v[j][i-1][0]][i-1][1]);
                v[j][i].push_back(max(v[j][i-1][2], v[v[j][i-1][0]][i-1][2]-v[j][i-1][1]));
			}
		}
	}
	return;
}

ll simulate(int x, int z){
	ll y = z;
    while (x != n){
		int i = 0;
		while (v[x][i][2] <= y){
            i++;
            if (v[x][i-1][0] == n) break;
        }
        if (i == 0){
            y += p[x];
            x = l[x];
        }
        else {
            y += v[x][i-1][1];
            x = v[x][i-1][0];
        }
	}
	return y;
}

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