Submission #1271316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271316		nerrrmin	Dungeons Game (IOI21_dungeons)	C++20	0 / 100	1 ms	840 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];
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;
    }
    for (int i = 0; i < n; ++ i)
    {
        jump[i][0] = lose[i];
        collect[i][0] = b[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];
        }
    }
}
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);
}
long long rec(long long pos, long long s)
{
    if(pos == nn)return s;
    if(s >= a[pos])return rec(win[pos], s+a[pos]);
    else return rec(lose[pos], s+b[pos]);
}
long long simulate(int x, int z)
{
    long long lt = 0, rt = 1e7, mid, ans = 1e7+1;
    while(lt <= rt)
    {
        mid = (lt + rt)/2;
        if(check(x, z, mid))
        {
            rt = mid - 1;
            ans = mid;
        }
        else lt = mid + 1;
    }
    assert(ans < 1e7+1);
    long long pos = x, power = z;
    for (int bit = 0; bit < 30; ++ bit)
    {
        if((1 << bit) & ans)
        {
            assert(pos != nn);
            pos = jump[pos][bit];

            power += collect[pos][bit];
        }
    }

	return rec(pos, power);
}

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