Submission #826546

#	Time	Username	Problem	Language	Result	Execution time	Memory
826546		TahirAliyev	Dungeons Game (IOI21_dungeons)	C++17	13 / 100	94 ms	41752 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<int, ll>

const int MAX = 5e4 + 5, LOGMAX = 25;

int N;
int S;

struct g{
    pii par[LOGMAX][MAX];
    void init(){
        for (int j = 1; j < LOGMAX; j++)
        {
            for (int i = 0; i <= N; i++)
            {
                int m = par[j - 1][i].first;
                par[j][i].first = par[j - 1][m].first;
                par[j][i].second = par[j - 1][i].second + par[j - 1][m].second;
            }
        }
    }
    pii lift(int u, int s){
        if(s >= S){
            return {u, s};
        }
        ll curs = s;
        int v = u;
        for (int j = LOGMAX - 1; j >= 0; j--)
        {
            if(curs + par[j][v].second < S){
                curs += par[j][v].second;
                v = par[j][v].first;
            }
        }
        return make_pair(par[0][v].first, par[0][v].second + curs);
    }
};


g G[2];



void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
    N = n;
    S = s[0];
	for (int i = 0; i < n; i++)
    {
        G[0].par[0][i] = {l[i], p[i]};
        G[1].par[0][i] = {w[i], S};
    }
    G[0].par[0][n] = {n, 0};
    G[1].par[0][n] = {n, 0};
    
    G[0].init();
    G[1].init();

}

ll simulate(int x, int z) {
	pii a = G[0].lift(x, z);
    return a.second + G[1].par[LOGMAX - 1][a.first].second;
}

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