Submission #1271337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271337		nerrrmin	Dungeons Game (IOI21_dungeons)	C++20	37 / 100	7096 ms	308088 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;
const int maxn = 4e5 + 10;
int nn;
vector < long long > a, b;
vector < long long > win, lose;
long long req, jump[maxn][30], collect[maxn][30], limit[maxn][30];
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
    nn = n;
    a.resize(n, 0);
    b.resize(n, 0);
    req = s[0];
    for (int i = 0; i < nn; ++ i)
        a[i] = s[i];
    for (int i = 0; i < nn; ++ i)
        b[i] = p[i];
    win.resize(n, 0);
    lose.resize(n, 0);
    for (int i = 0; i < nn; ++ i)
        win[i] = w[i];
    for (int i = 0; i < nn; ++ i)
        lose[i] = l[i];
    for (int j = 0; j < 30; ++ j)
    {
        jump[n][j] = n;
        collect[n][j] = 0;
        limit[n][j] = 0;
    }
    for (int i = n-1; i >= 0; -- i)
    {
        jump[i][0] = win[i];
        collect[i][0] = a[i];
        limit[i][0] = a[i];
    }
	for (int j = 1; j < 30; ++ j)
    {
        for (int i = 0; i < n; ++ i)
        {
            jump[i][j] = jump[jump[i][j-1]][j-1];
            collect[i][j] = collect[i][j-1] + collect[jump[i][j-1]][j-1];
            limit[i][j] = max(limit[i][j-1], limit[jump[i][j-1]][j-1] - collect[i][j-1]);
        }
    }
}
bool check(long long start, long long s, long long x)
{
    long long pos = start, power = s;
    for (int i = 29; i >= 0; -- i)
    {
        if((1 << i) & x)
        {
            power += collect[pos][i];
            pos = jump[pos][i];
            if(pos == nn)return 1;

            if(power >= req)return 1;
        }
    }
    return (power >= req);
}

pair < long long, long long > stimulate_losing(int pos, long long power)
{
    if(power >= a[pos])return make_pair(pos, power);
    return stimulate_losing(lose[pos], power + b[pos]);
}
long long simulate(int x, int z)
{
    long long pos = x, power = z;
    while(pos != nn)
    {

       // cout << pos << " " << power << endl;

        for (int bit = 29; bit >= 0; -- bit)
        {
            if(jump[pos][bit] > pos && limit[pos][bit] <= power)
            {
              //  cout << "movingggg " << endl;
                power += collect[pos][bit];
                pos = jump[pos][bit];
            }
        }


        if(pos == nn)return power;
        pair < long long, long long > op = stimulate_losing(pos, power);
        pos = op.first;
        power = op.second;
    }
	return power;
}

/***
3 2
2 6 9
3 1 2
2 2 3
1 0 1
0 1
2 3

*/

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