Submission #608742

#	Time	Username	Problem	Language	Result	Execution time	Memory
608742		Siffer	Dungeons Game (IOI21_dungeons)	C++17	13 / 100	154 ms	27812 KiB

dungeons

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

typedef long long ll;

#define F first
#define S second

int nn;
int ss;

vector<vector<pair<int,ll>>> bl;
vector<ll> last;

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
    ss = s[0];
    bl.resize(31, vector<pair<int,ll>>(n+1));
    bl[0][n] = {n,0};
    for(int i = 0; i < n; i++) bl[0][i] = {l[i], p[i]};
    for(int i = 1; i < 31; i++) for(int j = 0; j <= n; j++) bl[i][j] = {bl[i-1][bl[i-1][j].F].F, bl[i-1][j].S+bl[i-1][bl[i-1][j].F].S};
    last.resize(n+1,0);
    for(int i = n-1; i+1; i--) last[i] = last[w[i]] + s[0];
    /*for(int i = 0; i < 4; i++) {
        for(int j = 0; j <= n; j++) cout << "(" << bl[i][j].F << ", " << bl[i][j].S << ") ";
        cout << endl;
    }*/
}

ll simulate(int x, int z) {
    ll k = z;
    for(int i = 30; i+1; i--) if(k+bl[i][x].S < ss) k += bl[i][x].S, x = bl[i][x].F;
    //cout << "k: " << x << " " << k << endl;
    if(k < ss) k += bl[0][x].S, x = bl[0][x].F;
	return k+last[x];
}

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