Submission #608690

#	Time	Username	Problem	Language	Result	Execution time	Memory
608690		Siffer	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	3 ms	1364 KiB

dungeons

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

typedef long long ll;

#define F first
#define S second

int nn;

vector<int> ss, pp, ww, lll;
vector<vector<pair<int,ll>>> bl;
vector<ll> last;

ll ggg(int x) {
    if(~last[x]) return last[x];
    return last[x] = ss[x]+ggg(ww[x]);
}

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
    nn = n; ss.resize(n); pp.resize(n); ww.resize(n); lll.resize(n);
    for(int i = 0; i < n; i++) ss[i] = s[i], pp[i] = p[i], ww[i] = w[i], lll[i] = l[i];
    bl.resize(64, vector<pair<int,ll>>(n+1));
    bl[0][n] = {0,0};
    for(int i = 0; i < n; i++) bl[0][i] = {l[i], p[i]};
    for(int i = 1; i < 64; 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,-1);
    last[n] = 0;
    for(int i = 0; i < n; i++) ggg(i);
}

ll simulate(int x, int z) {
    ll k = z;
    for(int i = 63; i; i--) if(k+bl[i][x].S < ss[0]) k += bl[i][x].S, x = bl[i][x].F;
    k += bl[0][x].S; x = bl[0][x].F;
	return k+last[x];
}

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