oj.uz

Submission #935230

# Submission time Handle Problem Language Result Execution time Memory
935230 2024-02-28T22:46:57 Z jerzyk Dungeons Game (IOI21_dungeons) C++17
100 / 100
 2494 ms 1634876 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 240880 KB Output is correct
2 Correct 29 ms 238936 KB Output is correct
3 Correct 33 ms 245636 KB Output is correct
4 Correct 149 ms 410712 KB Output is correct
5 Correct 34 ms 245584 KB Output is correct
6 Correct 145 ms 410896 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 244312 KB Output is correct
2 Correct 1789 ms 1625612 KB Output is correct
3 Correct 1198 ms 1630036 KB Output is correct
4 Correct 1216 ms 1631360 KB Output is correct
5 Correct 1097 ms 1631572 KB Output is correct
6 Correct 1737 ms 1630300 KB Output is correct
7 Correct 1697 ms 1628240 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 272980 KB Output is correct
2 Correct 195 ms 434516 KB Output is correct
3 Correct 181 ms 433092 KB Output is correct
4 Correct 189 ms 432596 KB Output is correct
5 Correct 187 ms 432356 KB Output is correct
6 Correct 405 ms 432464 KB Output is correct
7 Correct 579 ms 432476 KB Output is correct
8 Correct 334 ms 432208 KB Output is correct
9 Correct 190 ms 432140 KB Output is correct
10 Correct 381 ms 432128 KB Output is correct
11 Correct 543 ms 430672 KB Output is correct
12 Correct 1552 ms 432700 KB Output is correct
13 Correct 1349 ms 430724 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 272980 KB Output is correct
2 Correct 195 ms 434516 KB Output is correct
3 Correct 181 ms 433092 KB Output is correct
4 Correct 189 ms 432596 KB Output is correct
5 Correct 187 ms 432356 KB Output is correct
6 Correct 405 ms 432464 KB Output is correct
7 Correct 579 ms 432476 KB Output is correct
8 Correct 334 ms 432208 KB Output is correct
9 Correct 190 ms 432140 KB Output is correct
10 Correct 381 ms 432128 KB Output is correct
11 Correct 543 ms 430672 KB Output is correct
12 Correct 1552 ms 432700 KB Output is correct
13 Correct 1349 ms 430724 KB Output is correct
14 Correct 34 ms 264752 KB Output is correct
15 Correct 191 ms 429196 KB Output is correct
16 Correct 201 ms 429272 KB Output is correct
17 Correct 218 ms 430588 KB Output is correct
18 Correct 230 ms 432452 KB Output is correct
19 Correct 413 ms 432516 KB Output is correct
20 Correct 365 ms 432328 KB Output is correct
21 Correct 397 ms 432388 KB Output is correct
22 Correct 471 ms 432460 KB Output is correct
23 Correct 848 ms 430672 KB Output is correct
24 Correct 870 ms 432580 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 272980 KB Output is correct
2 Correct 195 ms 434516 KB Output is correct
3 Correct 181 ms 433092 KB Output is correct
4 Correct 189 ms 432596 KB Output is correct
5 Correct 187 ms 432356 KB Output is correct
6 Correct 405 ms 432464 KB Output is correct
7 Correct 579 ms 432476 KB Output is correct
8 Correct 334 ms 432208 KB Output is correct
9 Correct 190 ms 432140 KB Output is correct
10 Correct 381 ms 432128 KB Output is correct
11 Correct 543 ms 430672 KB Output is correct
12 Correct 1552 ms 432700 KB Output is correct
13 Correct 1349 ms 430724 KB Output is correct
14 Correct 34 ms 264752 KB Output is correct
15 Correct 191 ms 429196 KB Output is correct
16 Correct 201 ms 429272 KB Output is correct
17 Correct 218 ms 430588 KB Output is correct
18 Correct 230 ms 432452 KB Output is correct
19 Correct 413 ms 432516 KB Output is correct
20 Correct 365 ms 432328 KB Output is correct
21 Correct 397 ms 432388 KB Output is correct
22 Correct 471 ms 432460 KB Output is correct
23 Correct 848 ms 430672 KB Output is correct
24 Correct 870 ms 432580 KB Output is correct
25 Correct 170 ms 431904 KB Output is correct
26 Correct 202 ms 433000 KB Output is correct
27 Correct 186 ms 432208 KB Output is correct
28 Correct 198 ms 432500 KB Output is correct
29 Correct 216 ms 432720 KB Output is correct
30 Correct 376 ms 432360 KB Output is correct
31 Correct 423 ms 432212 KB Output is correct
32 Correct 674 ms 432212 KB Output is correct
33 Correct 460 ms 432468 KB Output is correct
34 Correct 967 ms 432376 KB Output is correct
35 Correct 661 ms 432452 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 244312 KB Output is correct
2 Correct 1789 ms 1625612 KB Output is correct
3 Correct 1198 ms 1630036 KB Output is correct
4 Correct 1216 ms 1631360 KB Output is correct
5 Correct 1097 ms 1631572 KB Output is correct
6 Correct 1737 ms 1630300 KB Output is correct
7 Correct 1697 ms 1628240 KB Output is correct
8 Correct 34 ms 272980 KB Output is correct
9 Correct 195 ms 434516 KB Output is correct
10 Correct 181 ms 433092 KB Output is correct
11 Correct 189 ms 432596 KB Output is correct
12 Correct 187 ms 432356 KB Output is correct
13 Correct 405 ms 432464 KB Output is correct
14 Correct 579 ms 432476 KB Output is correct
15 Correct 334 ms 432208 KB Output is correct
16 Correct 190 ms 432140 KB Output is correct
17 Correct 381 ms 432128 KB Output is correct
18 Correct 543 ms 430672 KB Output is correct
19 Correct 1552 ms 432700 KB Output is correct
20 Correct 1349 ms 430724 KB Output is correct
21 Correct 34 ms 264752 KB Output is correct
22 Correct 191 ms 429196 KB Output is correct
23 Correct 201 ms 429272 KB Output is correct
24 Correct 218 ms 430588 KB Output is correct
25 Correct 230 ms 432452 KB Output is correct
26 Correct 413 ms 432516 KB Output is correct
27 Correct 365 ms 432328 KB Output is correct
28 Correct 397 ms 432388 KB Output is correct
29 Correct 471 ms 432460 KB Output is correct
30 Correct 848 ms 430672 KB Output is correct
31 Correct 870 ms 432580 KB Output is correct
32 Correct 170 ms 431904 KB Output is correct
33 Correct 202 ms 433000 KB Output is correct
34 Correct 186 ms 432208 KB Output is correct
35 Correct 198 ms 432500 KB Output is correct
36 Correct 216 ms 432720 KB Output is correct
37 Correct 376 ms 432360 KB Output is correct
38 Correct 423 ms 432212 KB Output is correct
39 Correct 674 ms 432212 KB Output is correct
40 Correct 460 ms 432468 KB Output is correct
41 Correct 967 ms 432376 KB Output is correct
42 Correct 661 ms 432452 KB Output is correct
43 Correct 34 ms 265592 KB Output is correct
44 Correct 34 ms 268888 KB Output is correct
45 Correct 1461 ms 1634140 KB Output is correct
46 Correct 1150 ms 1630176 KB Output is correct
47 Correct 1142 ms 1630456 KB Output is correct
48 Correct 1069 ms 1632568 KB Output is correct
49 Correct 1370 ms 1634876 KB Output is correct
50 Correct 1423 ms 1632352 KB Output is correct
51 Correct 1114 ms 1632552 KB Output is correct
52 Correct 1484 ms 1630544 KB Output is correct
53 Correct 2494 ms 1631216 KB Output is correct
54 Correct 1464 ms 1632312 KB Output is correct
55 Correct 2008 ms 1631348 KB Output is correct
56 Correct 2071 ms 1631980 KB Output is correct
57 Correct 1956 ms 1631748 KB Output is correct
58 Correct 2086 ms 1632084 KB Output is correct
59 Correct 2023 ms 1632232 KB Output is correct
60 Correct 2023 ms 1631312 KB Output is correct
61 Correct 1745 ms 1631356 KB Output is correct