Submission #623715

#	Time	Username	Problem	Language	Result	Execution time	Memory
623715		MohamedFaresNebili	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	3910 ms	1537312 KiB

dungeons

#include <bits/stdc++.h>

            using namespace std;
            using ll = long long;

            ll N, A[8][400005][20], B[8][400005][20], C[8][400005][20];
            ll S[400005], P[400005], W[400005], L[400005];

            void init(int n, vector<int> s, vector<int> p,
                      vector<int> w, vector<int> l) {
                N = n;
                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 l = 0; l < 8; l++)
                    for(int i = 0; i < 20; i++)
                        A[l][N][i] = N, B[l][N][i] = 0, C[l][N][i] = 1e9;
                ll cur = 1;
                for(int l = 0; l < 8; l++) {
                    for(int i = 0; i < N; i++) {
                        if(S[i] <= cur) A[l][i][0] = W[i], B[l][i][0] = S[i], C[l][i][0] = 1e9;
                        else A[l][i][0] = L[i], B[l][i][0] = P[i], C[l][i][0] = S[i];
                    }
                    for(int j = 1; j < 20; j++) {
                        for(int i = 0; i < N; i++) {
                            A[l][i][j] = A[l][A[l][i][j - 1]][j - 1];
                            B[l][i][j] = B[l][i][j - 1] + B[l][A[l][i][j - 1]][j - 1];
                            C[l][i][j] = C[l][i][j - 1];
                            if(C[l][A[l][i][j - 1]][j - 1] != 1e9)
                                C[l][i][j] = min(C[l][i][j], max(C[l][A[l][i][j - 1]][j - 1] - B[l][i][j - 1], 0ll));
                        }
                    }
                    cur *= 10;
                }
            }

            long long simulate(int x, int t) {
                ll cur = 1, lvl = 0, z = t;
                while(x != N) {
                    while(lvl < 7 && cur * 10 <= z) lvl++, cur *= 10;
                    for(int l = 18; l >= 0; l--) {
                        if(A[lvl][x][l] != N && min((ll)1e7, z) < C[lvl][x][l])
                            z += B[lvl][x][l], x = A[lvl][x][l];
                    }
                    if(z < S[x]) z += P[x], x = L[x];
                    else z += S[x], x = W[x];
                }
                return z;
            }

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