Submission #935230

#	Time	Username	Problem	Language	Result	Execution time	Memory
935230		jerzyk	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	2494 ms	1634876 KiB

dungeons

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

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const int I = 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 400 * 1000 + 7;
const int K = 16;
int pot3[K + 2];
int ts[N], tp[N], le[N], we[N];
int jp[K][K][N], req[K][K][N];
ll sum[K][K][N];
int n;

void DoP()
{
    pot3[0] = 1;
    for(int i = 1; i < K; ++i) pot3[i] = 3 * pot3[i - 1];
}

inline int P3(int x)
{
    if(x == 0) return 0;
    return (upper_bound(pot3, pot3 + K, x) - pot3) - 1;
}

void DoLCA(int n)
{
    le[n + 1] = n + 1; we[n + 1] = n + 1;
    for(int i = 0; i < K; ++i)
        for(int j = 0; j < K; ++j)
        {
            sum[i][j][n + 1] = 0;
            jp[i][j][n + 1] = n + 1;
            req[i][j][n + 1] = -1;
        }
    for(int i = 1; i <= n; ++i)
    {
        int x = P3(ts[i]);
        for(int j = 0; j < x; ++j)
        {
            req[j][0][i] = max(-1, 3 * pot3[j] -  tp[i] - 1);
            sum[j][0][i] = tp[i];
            jp[j][0][i] = le[i];
        }
        req[x][0][i] = min(ts[i] - 1, 3 * pot3[x] - tp[i] - 1);
        req[x][0][i] = max(req[x][0][i], -1);
        sum[x][0][i] = tp[i];
        jp[x][0][i] = le[i];
        for(int j = x + 1; j < K; ++j)
        {
            req[j][0][i] = 3 * pot3[j] - 1 - ts[i];
            sum[j][0][i] = ts[i];
            jp[j][0][i] = we[i];
        }
    }
    for(int j = 0; j < K; ++j)
        for(int k = 1; k < K; ++k)
            for(int i = 1; i <= n; ++i)
            {
                jp[j][k][i] = jp[j][k - 1][i];
                sum[j][k][i] = sum[j][k - 1][i];
                req[j][k][i] = req[j][k - 1][i];
                for(int l = 1; l <= 2; ++l)
                {
                    int ne = jp[j][k][i];
                    req[j][k][i] = max(-1LL, min((ll)req[j][k][i], (ll)req[j][k - 1][ne] - sum[j][k][i]));
                    sum[j][k][i] += sum[j][k - 1][ne];
                    jp[j][k][i] = jp[j][k - 1][ne];
                }
            }
}

ll Ans(int v, ll x, int n)
{
    int j = 0;
    while(v != n + 1)
    {
        while(j < K - 1 && pot3[j + 1] <= x) ++j;
        for(int k = K - 1; k >= 0; --k)
            for(int l = 1; l <= 2; ++l)
            {
                //if(k < 4)
                    //cout << j << " " << k << " " << v << " " << x << " : " << sum[j][k][v] << " " << req[j][k][v] << " " << jp[j][k][v] << "\n";
                if(j == K - 1 || x <= req[j][k][v])
                {
                    x += sum[j][k][v];
                    v = jp[j][k][v];
                }
            }
        if(x >= (ll)ts[v])
        {
            x += (ll)ts[v];
            v = we[v];
        }else
        {
            x += (ll)tp[v];
            v = le[v];
        }
    }
    return x;
}

void init(int nx, vector<int> s, vector<int> p, vector<int> w, vector<int> l) 
{
    DoP(); n = nx;
    for(int i = 1; i <= n; ++i)
    {
        ts[i] = s[i - 1]; tp[i] = p[i - 1];
        we[i] = w[i - 1] + 1; le[i] = l[i - 1] + 1;
    }
    DoLCA(n);
    return;
}

ll simulate(int x, int z)
{
    int v = x + 1; x = z;
    ll ans = Ans(v, x, n);
    return ans;
}

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