oj.uz

Submission #981458

# Submission time Handle Problem Language Result Execution time Memory
981458 2024-05-13T08:34:09 Z 12345678 Dungeons Game (IOI21_dungeons) C++17
100 / 100
 3624 ms 1913652 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=4e5+5, lx=8, kx=25;

ll N, pw[20], dist[nx];
vector<int> S(nx), P(nx), W(nx), L(nx);

struct edge
{
    int out;
    ll cost, t;
    edge(int out=0, ll cost=0, ll t=0): out(out), cost(cost), t(t){}
} dp[lx][nx][kx];

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
    N=n;
    pw[0]=1;
    for (int i=1; i<20; i++) pw[i]=pw[i-1]*8;
    for (int i=0; i<n; i++) S[i]=s[i], P[i]=p[i], W[i]=w[i], L[i]=l[i];
    for (int i=n-1; i>=0; i--) dist[i]=dist[w[i]]+s[i];
    W[n]=L[n]=n;
    for (int i=0; i<lx; i++)
    {
        for (int u=0; u<=n; u++)
        {
            if (s[u]<=pw[i]) dp[i][u][0]=edge(W[u], S[u], 1e18);
            else dp[i][u][0]=edge(L[u], P[u], S[u]);
        }
        for (int j=1; j<kx; j++)
        {
            for (int u=0; u<=n; u++)
            {
                int v=dp[i][u][j-1].out;
                ll out=dp[i][v][j-1].out;
                ll cost=dp[i][u][j-1].cost+dp[i][v][j-1].cost;
                ll t=min(dp[i][u][j-1].t, dp[i][v][j-1].t-dp[i][u][j-1].cost);
                dp[i][u][j]=edge(out, cost, t);
            }
        }
    }
}

long long simulate(int x, int z) {
    ll cur=z, st=0;
    while (x!=N&&cur<1e7)
    {
        //cout<<"debug "<<x<<' '<<cur<<' '<<st<<'\n';
        while (st+1<lx&&pw[st+1]<=cur) st++;
        for (int i=kx-1; i>=0; i--) if (dp[st][x][i].t>cur) cur+=dp[st][x][i].cost, x=dp[st][x][i].out; //cout<<"here "<<i<<' '<<cur<<' '<<x<<'\n';
        //cout<<"after "<<x<<' '<<cur<<' '<<st<<'\n';
        if (cur>=S[x]) cur+=S[x], x=W[x];
        else cur+=P[x], x=L[x];
    }
	return cur+dist[x];
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 925 ms 1886376 KB Output is correct
2 Correct 650 ms 1886320 KB Output is correct
3 Correct 623 ms 1886612 KB Output is correct
4 Correct 740 ms 1889120 KB Output is correct
5 Correct 677 ms 1886404 KB Output is correct
6 Correct 735 ms 1889104 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 766 ms 1886548 KB Output is correct
2 Correct 2430 ms 1902324 KB Output is correct
3 Correct 2177 ms 1908724 KB Output is correct
4 Correct 2138 ms 1910256 KB Output is correct
5 Correct 2087 ms 1908232 KB Output is correct
6 Correct 2380 ms 1904436 KB Output is correct
7 Correct 2222 ms 1903696 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 1886324 KB Output is correct
2 Correct 723 ms 1889552 KB Output is correct
3 Correct 712 ms 1889596 KB Output is correct
4 Correct 708 ms 1889928 KB Output is correct
5 Correct 710 ms 1889912 KB Output is correct
6 Correct 746 ms 1890108 KB Output is correct
7 Correct 752 ms 1890132 KB Output is correct
8 Correct 695 ms 1889872 KB Output is correct
9 Correct 710 ms 1889828 KB Output is correct
10 Correct 704 ms 1889496 KB Output is correct
11 Correct 740 ms 1890148 KB Output is correct
12 Correct 818 ms 1890020 KB Output is correct
13 Correct 809 ms 1890252 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 1886324 KB Output is correct
2 Correct 723 ms 1889552 KB Output is correct
3 Correct 712 ms 1889596 KB Output is correct
4 Correct 708 ms 1889928 KB Output is correct
5 Correct 710 ms 1889912 KB Output is correct
6 Correct 746 ms 1890108 KB Output is correct
7 Correct 752 ms 1890132 KB Output is correct
8 Correct 695 ms 1889872 KB Output is correct
9 Correct 710 ms 1889828 KB Output is correct
10 Correct 704 ms 1889496 KB Output is correct
11 Correct 740 ms 1890148 KB Output is correct
12 Correct 818 ms 1890020 KB Output is correct
13 Correct 809 ms 1890252 KB Output is correct
14 Correct 606 ms 1886632 KB Output is correct
15 Correct 859 ms 1890368 KB Output is correct
16 Correct 909 ms 1890596 KB Output is correct
17 Correct 731 ms 1889868 KB Output is correct
18 Correct 761 ms 1890184 KB Output is correct
19 Correct 719 ms 1889988 KB Output is correct
20 Correct 711 ms 1889856 KB Output is correct
21 Correct 731 ms 1889884 KB Output is correct
22 Correct 719 ms 1889996 KB Output is correct
23 Correct 721 ms 1890008 KB Output is correct
24 Correct 870 ms 1890084 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 657 ms 1886324 KB Output is correct
2 Correct 723 ms 1889552 KB Output is correct
3 Correct 712 ms 1889596 KB Output is correct
4 Correct 708 ms 1889928 KB Output is correct
5 Correct 710 ms 1889912 KB Output is correct
6 Correct 746 ms 1890108 KB Output is correct
7 Correct 752 ms 1890132 KB Output is correct
8 Correct 695 ms 1889872 KB Output is correct
9 Correct 710 ms 1889828 KB Output is correct
10 Correct 704 ms 1889496 KB Output is correct
11 Correct 740 ms 1890148 KB Output is correct
12 Correct 818 ms 1890020 KB Output is correct
13 Correct 809 ms 1890252 KB Output is correct
14 Correct 606 ms 1886632 KB Output is correct
15 Correct 859 ms 1890368 KB Output is correct
16 Correct 909 ms 1890596 KB Output is correct
17 Correct 731 ms 1889868 KB Output is correct
18 Correct 761 ms 1890184 KB Output is correct
19 Correct 719 ms 1889988 KB Output is correct
20 Correct 711 ms 1889856 KB Output is correct
21 Correct 731 ms 1889884 KB Output is correct
22 Correct 719 ms 1889996 KB Output is correct
23 Correct 721 ms 1890008 KB Output is correct
24 Correct 870 ms 1890084 KB Output is correct
25 Correct 701 ms 1889560 KB Output is correct
26 Correct 746 ms 1890376 KB Output is correct
27 Correct 723 ms 1889880 KB Output is correct
28 Correct 694 ms 1890212 KB Output is correct
29 Correct 735 ms 1890452 KB Output is correct
30 Correct 740 ms 1890164 KB Output is correct
31 Correct 749 ms 1890052 KB Output is correct
32 Correct 815 ms 1889872 KB Output is correct
33 Correct 887 ms 1890120 KB Output is correct
34 Correct 1283 ms 1889988 KB Output is correct
35 Correct 803 ms 1889780 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 766 ms 1886548 KB Output is correct
2 Correct 2430 ms 1902324 KB Output is correct
3 Correct 2177 ms 1908724 KB Output is correct
4 Correct 2138 ms 1910256 KB Output is correct
5 Correct 2087 ms 1908232 KB Output is correct
6 Correct 2380 ms 1904436 KB Output is correct
7 Correct 2222 ms 1903696 KB Output is correct
8 Correct 657 ms 1886324 KB Output is correct
9 Correct 723 ms 1889552 KB Output is correct
10 Correct 712 ms 1889596 KB Output is correct
11 Correct 708 ms 1889928 KB Output is correct
12 Correct 710 ms 1889912 KB Output is correct
13 Correct 746 ms 1890108 KB Output is correct
14 Correct 752 ms 1890132 KB Output is correct
15 Correct 695 ms 1889872 KB Output is correct
16 Correct 710 ms 1889828 KB Output is correct
17 Correct 704 ms 1889496 KB Output is correct
18 Correct 740 ms 1890148 KB Output is correct
19 Correct 818 ms 1890020 KB Output is correct
20 Correct 809 ms 1890252 KB Output is correct
21 Correct 606 ms 1886632 KB Output is correct
22 Correct 859 ms 1890368 KB Output is correct
23 Correct 909 ms 1890596 KB Output is correct
24 Correct 731 ms 1889868 KB Output is correct
25 Correct 761 ms 1890184 KB Output is correct
26 Correct 719 ms 1889988 KB Output is correct
27 Correct 711 ms 1889856 KB Output is correct
28 Correct 731 ms 1889884 KB Output is correct
29 Correct 719 ms 1889996 KB Output is correct
30 Correct 721 ms 1890008 KB Output is correct
31 Correct 870 ms 1890084 KB Output is correct
32 Correct 701 ms 1889560 KB Output is correct
33 Correct 746 ms 1890376 KB Output is correct
34 Correct 723 ms 1889880 KB Output is correct
35 Correct 694 ms 1890212 KB Output is correct
36 Correct 735 ms 1890452 KB Output is correct
37 Correct 740 ms 1890164 KB Output is correct
38 Correct 749 ms 1890052 KB Output is correct
39 Correct 815 ms 1889872 KB Output is correct
40 Correct 887 ms 1890120 KB Output is correct
41 Correct 1283 ms 1889988 KB Output is correct
42 Correct 803 ms 1889780 KB Output is correct
43 Correct 592 ms 1886288 KB Output is correct
44 Correct 598 ms 1886512 KB Output is correct
45 Correct 2217 ms 1913484 KB Output is correct
46 Correct 2091 ms 1908880 KB Output is correct
47 Correct 2085 ms 1909260 KB Output is correct
48 Correct 2043 ms 1911440 KB Output is correct
49 Correct 2239 ms 1913652 KB Output is correct
50 Correct 2412 ms 1911056 KB Output is correct
51 Correct 2072 ms 1911480 KB Output is correct
52 Correct 2342 ms 1909284 KB Output is correct
53 Correct 2832 ms 1909900 KB Output is correct
54 Correct 2794 ms 1911108 KB Output is correct
55 Correct 3624 ms 1910304 KB Output is correct
56 Correct 2582 ms 1910672 KB Output is correct
57 Correct 2985 ms 1910752 KB Output is correct
58 Correct 2766 ms 1910800 KB Output is correct
59 Correct 2696 ms 1910924 KB Output is correct
60 Correct 3288 ms 1910160 KB Output is correct
61 Correct 3245 ms 1910160 KB Output is correct