oj.uz

Submission #442857

# Submission time Handle Problem Language Result Execution time Memory
442857 2021-07-09T09:30:13 Z baluteshih Dungeons Game (IOI21_dungeons) C++17
50 / 100
 7000 ms 395748 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define SZ(a) ((int)a.size())

const int MAXC = 10000000;
struct node {
    int to, lower;
    ll sum;
    node operator+(const node &a) const {
        node rt;
        rt.to = a.to;
        rt.sum = sum + a.sum;
        if (lower + sum < a.lower)
            rt.lower = a.lower - sum;
        else
            rt.lower = lower;
        return rt;
    }
};

struct node2 {
    int to;
    ll upper, sum;
    node2 operator+(const node2 &a) const {
        node2 rt;
        rt.to = a.to;
        rt.sum = sum + a.sum;
        if (a.upper == MAXC + 1)
            rt.upper = upper;
        else if (upper + sum > a.upper)
            rt.upper = a.upper - sum;
        else
            rt.upper = upper;
        return rt;
    }
};

int N, lg = __lg(MAXC);
vector<int> S, P, W, L;
vector<node> dp[30];
vector<node2> dp2[30];

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;
    dp[0].resize(N + 1);
    dp[0][N] = node{N, 0, 0};
    for (int i = 0; i < N; ++i)
       dp[0][i] = node{W[i], S[i], (ll)S[i]};
    for (int i = 1; i <= lg; ++i) {
        dp[i].resize(N + 1);
        for (int j = 0; j <= N; ++j)
            dp[i][j] = dp[i - 1][j] + dp[i - 1][dp[i - 1][j].to];
    }
    dp2[0].resize(N + 1);
    dp2[0][N] = node2{N, 0LL, 0LL};
    for (int i = 0; i < N; ++i)
       dp2[0][i] = node2{L[i], S[i] - 1, (ll)P[i]};
    for (int i = 1; i <= lg; ++i) {
        dp2[i].resize(N + 1);
        for (int j = 0; j <= N; ++j)
            dp2[i][j] = dp2[i - 1][j] + dp2[i - 1][dp2[i - 1][j].to];
    }
}

long long simulate(int x, int z) {
    ll nw = z;
    while (dp[lg][x].lower > nw) {
        for (int i = lg; i >= 0; --i)
            if (dp[i][x].lower <= nw) {
                nw += dp[i][x].sum;
                x = dp[i][x].to;
            }
        for (int i = lg; i >= 0; --i)
            if (dp2[i][x].upper >= nw) {
                nw += dp2[i][x].sum;
                x = dp2[i][x].to;
            }
    }
    return nw + dp[lg][x].sum;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 3 ms 2252 KB Output is correct
4 Correct 57 ms 49592 KB Output is correct
5 Correct 3 ms 2252 KB Output is correct
6 Correct 56 ms 49584 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1228 KB Output is correct
2 Correct 565 ms 395732 KB Output is correct
3 Correct 484 ms 395748 KB Output is correct
4 Correct 484 ms 395588 KB Output is correct
5 Correct 580 ms 395576 KB Output is correct
6 Correct 570 ms 395600 KB Output is correct
7 Correct 508 ms 395560 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1228 KB Output is correct
2 Correct 101 ms 50512 KB Output is correct
3 Correct 109 ms 50412 KB Output is correct
4 Correct 74 ms 50372 KB Output is correct
5 Correct 74 ms 50376 KB Output is correct
6 Correct 130 ms 50368 KB Output is correct
7 Correct 128 ms 51040 KB Output is correct
8 Correct 83 ms 50944 KB Output is correct
9 Correct 88 ms 50944 KB Output is correct
10 Correct 74 ms 50904 KB Output is correct
11 Correct 142 ms 51012 KB Output is correct
12 Correct 195 ms 51040 KB Output is correct
13 Correct 185 ms 51012 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1228 KB Output is correct
2 Correct 101 ms 50512 KB Output is correct
3 Correct 109 ms 50412 KB Output is correct
4 Correct 74 ms 50372 KB Output is correct
5 Correct 74 ms 50376 KB Output is correct
6 Correct 130 ms 50368 KB Output is correct
7 Correct 128 ms 51040 KB Output is correct
8 Correct 83 ms 50944 KB Output is correct
9 Correct 88 ms 50944 KB Output is correct
10 Correct 74 ms 50904 KB Output is correct
11 Correct 142 ms 51012 KB Output is correct
12 Correct 195 ms 51040 KB Output is correct
13 Correct 185 ms 51012 KB Output is correct
14 Correct 2 ms 1228 KB Output is correct
15 Correct 332 ms 50836 KB Output is correct
16 Correct 106 ms 51100 KB Output is correct
17 Correct 86 ms 51052 KB Output is correct
18 Correct 80 ms 50704 KB Output is correct
19 Correct 168 ms 50756 KB Output is correct
20 Correct 136 ms 50672 KB Output is correct
21 Correct 106 ms 50756 KB Output is correct
22 Execution timed out 7041 ms 50664 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1228 KB Output is correct
2 Correct 101 ms 50512 KB Output is correct
3 Correct 109 ms 50412 KB Output is correct
4 Correct 74 ms 50372 KB Output is correct
5 Correct 74 ms 50376 KB Output is correct
6 Correct 130 ms 50368 KB Output is correct
7 Correct 128 ms 51040 KB Output is correct
8 Correct 83 ms 50944 KB Output is correct
9 Correct 88 ms 50944 KB Output is correct
10 Correct 74 ms 50904 KB Output is correct
11 Correct 142 ms 51012 KB Output is correct
12 Correct 195 ms 51040 KB Output is correct
13 Correct 185 ms 51012 KB Output is correct
14 Correct 2 ms 1228 KB Output is correct
15 Correct 332 ms 50836 KB Output is correct
16 Correct 106 ms 51100 KB Output is correct
17 Correct 86 ms 51052 KB Output is correct
18 Correct 80 ms 50704 KB Output is correct
19 Correct 168 ms 50756 KB Output is correct
20 Correct 136 ms 50672 KB Output is correct
21 Correct 106 ms 50756 KB Output is correct
22 Execution timed out 7041 ms 50664 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1228 KB Output is correct
2 Correct 565 ms 395732 KB Output is correct
3 Correct 484 ms 395748 KB Output is correct
4 Correct 484 ms 395588 KB Output is correct
5 Correct 580 ms 395576 KB Output is correct
6 Correct 570 ms 395600 KB Output is correct
7 Correct 508 ms 395560 KB Output is correct
8 Correct 2 ms 1228 KB Output is correct
9 Correct 101 ms 50512 KB Output is correct
10 Correct 109 ms 50412 KB Output is correct
11 Correct 74 ms 50372 KB Output is correct
12 Correct 74 ms 50376 KB Output is correct
13 Correct 130 ms 50368 KB Output is correct
14 Correct 128 ms 51040 KB Output is correct
15 Correct 83 ms 50944 KB Output is correct
16 Correct 88 ms 50944 KB Output is correct
17 Correct 74 ms 50904 KB Output is correct
18 Correct 142 ms 51012 KB Output is correct
19 Correct 195 ms 51040 KB Output is correct
20 Correct 185 ms 51012 KB Output is correct
21 Correct 2 ms 1228 KB Output is correct
22 Correct 332 ms 50836 KB Output is correct
23 Correct 106 ms 51100 KB Output is correct
24 Correct 86 ms 51052 KB Output is correct
25 Correct 80 ms 50704 KB Output is correct
26 Correct 168 ms 50756 KB Output is correct
27 Correct 136 ms 50672 KB Output is correct
28 Correct 106 ms 50756 KB Output is correct
29 Execution timed out 7041 ms 50664 KB Time limit exceeded
30 Halted 0 ms 0 KB -