oj.uz

Submission #1046536

# Submission time Handle Problem Language Result Execution time Memory
1046536 2024-08-06T16:19:30 Z VMaksimoski008 Dungeons Game (IOI21_dungeons) C++17
50 / 100
 7000 ms 268884 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 6e5 + 5;
const int LOG = 25;
vector<int> S, P, W, L;
ll N, sub3 = 1, sub2 = 1, up[maxn][LOG];
ll sum[maxn][LOG], dist[maxn], mx[maxn][LOG];

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
    N = n;
    S = s;
    P = p;
    W = w;
    L = l;

    for(int i=1; i<N; i++) if(S[i] != S[i-1]) sub3 = 0;
    for(int i=0; i<N; i++) if(S[i] != P[i]) sub2 = 0;
    for(int i=N-1; i>=0; i--) dist[i] = dist[W[i]] + S[i];
    if(sub3) {
        for(int i=0; i<N; i++) up[i][0] = L[i], sum[i][0] = P[i];
        up[N][0] = N;

        for(int j=1; j<LOG; j++)
            for(int i=0; i<=N; i++) up[i][j] = up[up[i][j-1]][j-1];
        for(int j=1; j<LOG; j++)
            for(int i=0; i<=N; i++) sum[i][j] = sum[i][j-1] + sum[up[i][j-1]][j-1];
    } else {
        for(int i=0; i<N; i++) up[i][0] = W[i], sum[i][0] = mx[i][0] = S[i];
        up[N][0] = N;

        for(int j=1; j<LOG; j++)
            for(int i=0; i<=N; i++) up[i][j] = up[up[i][j-1]][j-1];
        for(int j=1; j<LOG; j++)
            for(int i=0; i<=N; i++) sum[i][j] = sum[i][j-1] + sum[up[i][j-1]][j-1];
        for(int j=1; j<LOG; j++)
            for(int i=0; i<=N; i++) mx[i][j] = max(mx[i][j-1], mx[up[i][j-1]][j-1] - sum[i][j-1]);
    }
	return;
}

ll simulate(int x, int z) {
    //moze samo min(n, log 10^7) pati da izgubime (so sekoja zaguba, silata barem se duplira)
    //ako si na pozicija da gubis, simulacija
    //ako si na poz da pobedis, bin jumping
    if(sub2) {
        ll ans = z;

        while(true) {
            if(ans < S[x]) {
                ans += P[x];
                x = L[x];
                continue;
            }

            for(int j=LOG-1; j>=0; j--) {
                if(ans >= mx[x][j]) {
                    ans += sum[x][j];
                    x = up[x][j];
                }
            }

            if(x == N) return ans;
        }

        return ans;
    }

    if(sub3) {
        if(z >= S[x]) return (ll)z + dist[x];
        ll ans = z;

        for(int i=LOG-1; i>=0; i--) {
            if(ans + sum[x][i] < S[x]) {
                ans += sum[x][i];
                x = up[x][i];
            }
        }

        if(x == N) return ans;
        if(ans < S[x]) ans += P[x], x = up[x][0];
        return ans + dist[x];
    }

    ll ans = z;
    while(x != N) {
        if(z >= S[x]) {
            z += S[x];
            x = W[x];
        } else {
            z += P[x];
            x = L[x];
        }
    }
	return z;
}

Compilation message

dungeons.cpp: In function 'll simulate(int, int)':
dungeons.cpp:87:8: warning: unused variable 'ans' [-Wunused-variable]
   87 |     ll ans = z;
      |        ^~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 26 ms 38804 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 26 ms 39016 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 389 ms 264192 KB Output is correct
3 Correct 379 ms 267324 KB Output is correct
4 Correct 382 ms 268884 KB Output is correct
5 Correct 379 ms 268884 KB Output is correct
6 Correct 401 ms 267368 KB Output is correct
7 Correct 384 ms 265556 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4456 KB Output is correct
2 Correct 33 ms 29612 KB Output is correct
3 Correct 33 ms 29524 KB Output is correct
4 Correct 29 ms 29324 KB Output is correct
5 Correct 28 ms 29020 KB Output is correct
6 Correct 33 ms 29340 KB Output is correct
7 Correct 34 ms 29268 KB Output is correct
8 Correct 28 ms 29276 KB Output is correct
9 Correct 28 ms 29276 KB Output is correct
10 Correct 28 ms 29268 KB Output is correct
11 Correct 29 ms 29264 KB Output is correct
12 Correct 49 ms 29204 KB Output is correct
13 Correct 39 ms 29264 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4456 KB Output is correct
2 Correct 33 ms 29612 KB Output is correct
3 Correct 33 ms 29524 KB Output is correct
4 Correct 29 ms 29324 KB Output is correct
5 Correct 28 ms 29020 KB Output is correct
6 Correct 33 ms 29340 KB Output is correct
7 Correct 34 ms 29268 KB Output is correct
8 Correct 28 ms 29276 KB Output is correct
9 Correct 28 ms 29276 KB Output is correct
10 Correct 28 ms 29268 KB Output is correct
11 Correct 29 ms 29264 KB Output is correct
12 Correct 49 ms 29204 KB Output is correct
13 Correct 39 ms 29264 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 85 ms 39980 KB Output is correct
16 Correct 42 ms 39760 KB Output is correct
17 Correct 1107 ms 39504 KB Output is correct
18 Correct 1180 ms 39508 KB Output is correct
19 Correct 4891 ms 39780 KB Output is correct
20 Correct 2074 ms 40028 KB Output is correct
21 Correct 2003 ms 40024 KB Output is correct
22 Correct 962 ms 40280 KB Output is correct
23 Execution timed out 7059 ms 40028 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4456 KB Output is correct
2 Correct 33 ms 29612 KB Output is correct
3 Correct 33 ms 29524 KB Output is correct
4 Correct 29 ms 29324 KB Output is correct
5 Correct 28 ms 29020 KB Output is correct
6 Correct 33 ms 29340 KB Output is correct
7 Correct 34 ms 29268 KB Output is correct
8 Correct 28 ms 29276 KB Output is correct
9 Correct 28 ms 29276 KB Output is correct
10 Correct 28 ms 29268 KB Output is correct
11 Correct 29 ms 29264 KB Output is correct
12 Correct 49 ms 29204 KB Output is correct
13 Correct 39 ms 29264 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 85 ms 39980 KB Output is correct
16 Correct 42 ms 39760 KB Output is correct
17 Correct 1107 ms 39504 KB Output is correct
18 Correct 1180 ms 39508 KB Output is correct
19 Correct 4891 ms 39780 KB Output is correct
20 Correct 2074 ms 40028 KB Output is correct
21 Correct 2003 ms 40024 KB Output is correct
22 Correct 962 ms 40280 KB Output is correct
23 Execution timed out 7059 ms 40028 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 389 ms 264192 KB Output is correct
3 Correct 379 ms 267324 KB Output is correct
4 Correct 382 ms 268884 KB Output is correct
5 Correct 379 ms 268884 KB Output is correct
6 Correct 401 ms 267368 KB Output is correct
7 Correct 384 ms 265556 KB Output is correct
8 Correct 1 ms 4456 KB Output is correct
9 Correct 33 ms 29612 KB Output is correct
10 Correct 33 ms 29524 KB Output is correct
11 Correct 29 ms 29324 KB Output is correct
12 Correct 28 ms 29020 KB Output is correct
13 Correct 33 ms 29340 KB Output is correct
14 Correct 34 ms 29268 KB Output is correct
15 Correct 28 ms 29276 KB Output is correct
16 Correct 28 ms 29276 KB Output is correct
17 Correct 28 ms 29268 KB Output is correct
18 Correct 29 ms 29264 KB Output is correct
19 Correct 49 ms 29204 KB Output is correct
20 Correct 39 ms 29264 KB Output is correct
21 Correct 1 ms 6748 KB Output is correct
22 Correct 85 ms 39980 KB Output is correct
23 Correct 42 ms 39760 KB Output is correct
24 Correct 1107 ms 39504 KB Output is correct
25 Correct 1180 ms 39508 KB Output is correct
26 Correct 4891 ms 39780 KB Output is correct
27 Correct 2074 ms 40028 KB Output is correct
28 Correct 2003 ms 40024 KB Output is correct
29 Correct 962 ms 40280 KB Output is correct
30 Execution timed out 7059 ms 40028 KB Time limit exceeded
31 Halted 0 ms 0 KB -