oj.uz

Submission #609302

# Submission time Handle Problem Language Result Execution time Memory
609302 2022-07-27T13:29:30 Z lorenzoferrari Dungeons Game (IOI21_dungeons) C++17
50 / 100
 7000 ms 437440 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using LL = long long;

constexpr int LG = 22;

struct nd {
    int v;  // final node
    LL inc; // total str increase
    LL ini; // min/max str needed so far
};
nd wjoin(nd a, nd b) {
    nd ans;
    ans.v = b.v;
    ans.inc = a.inc + b.inc;
    ans.ini = max(a.ini, b.ini - a.inc);
    return ans;
}
nd ljoin(nd a, nd b) {
    nd ans;
    ans.v = b.v;
    ans.inc = a.inc + b.inc;
    ans.ini = min(a.ini, b.ini - a.inc);
    return ans;
}

int n;
vi s, p, w, l;

vector<array<nd, LG>> wlift;
vector<array<nd, LG>> llift;

void init(int n, vi s, vi p, vi w, vi l) {
    ::n = n;
    s.push_back(0);
    p.push_back(0);
    w.push_back(n);
    l.push_back(n);
    ::s = s, ::p = p, ::w = w, ::l = l;
    wlift.resize(n+1);
    llift.resize(n+1);
    for (int i = 0; i < n; ++i) {
        wlift[i][0].v = w[i];
        llift[i][0].v = l[i];
        wlift[i][0].inc = s[i];
        llift[i][0].inc = p[i];
        wlift[i][0].ini = s[i];
        llift[i][0].ini = s[i] - 1;
    }
    wlift[n][0] = {n, 0, 0};
    llift[n][0] = {n, 0, 0};
    for (int i = 1; i < LG; ++i) {
        for (int j = 0; j <= n; ++j) {
            int wm = wlift[j][i-1].v;
            int lm = llift[j][i-1].v;
            wlift[j][i] = wjoin(wlift[j][i-1], wlift[wm][i-1]);
            llift[j][i] = ljoin(llift[j][i-1], llift[lm][i-1]);
        }
    }
}

void keep_winning(int& x, LL& z) {
    for (int i = LG-1; i >= 0; --i) {
        if (z >= wlift[x][i].ini) {
            z += wlift[x][i].inc;
            x = wlift[x][i].v;
        }
    }
}

void keep_losing(int& x, LL& z) {
    for (int i = LG-1; i >= 0; --i) {
        if (z <= llift[x][i].ini) {
            z += llift[x][i].inc;
            x = llift[x][i].v;
        }
    }
}

LL simulate(int x, int zi) {
    LL z = zi;
    int i = x;
	while (i != n) {
        keep_winning(i, z);
        keep_losing(i, z);
    }
    return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 2488 KB Output is correct
4 Correct 72 ms 55168 KB Output is correct
5 Correct 4 ms 2428 KB Output is correct
6 Correct 74 ms 55100 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1364 KB Output is correct
2 Correct 693 ms 435740 KB Output is correct
3 Correct 626 ms 437236 KB Output is correct
4 Correct 652 ms 437220 KB Output is correct
5 Correct 669 ms 437372 KB Output is correct
6 Correct 757 ms 437440 KB Output is correct
7 Correct 624 ms 436944 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1364 KB Output is correct
2 Correct 107 ms 55748 KB Output is correct
3 Correct 117 ms 56284 KB Output is correct
4 Correct 106 ms 56224 KB Output is correct
5 Correct 98 ms 56108 KB Output is correct
6 Correct 110 ms 56368 KB Output is correct
7 Correct 121 ms 56352 KB Output is correct
8 Correct 102 ms 56032 KB Output is correct
9 Correct 96 ms 55984 KB Output is correct
10 Correct 100 ms 55932 KB Output is correct
11 Correct 128 ms 56340 KB Output is correct
12 Correct 417 ms 56412 KB Output is correct
13 Correct 414 ms 56252 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1364 KB Output is correct
2 Correct 107 ms 55748 KB Output is correct
3 Correct 117 ms 56284 KB Output is correct
4 Correct 106 ms 56224 KB Output is correct
5 Correct 98 ms 56108 KB Output is correct
6 Correct 110 ms 56368 KB Output is correct
7 Correct 121 ms 56352 KB Output is correct
8 Correct 102 ms 56032 KB Output is correct
9 Correct 96 ms 55984 KB Output is correct
10 Correct 100 ms 55932 KB Output is correct
11 Correct 128 ms 56340 KB Output is correct
12 Correct 417 ms 56412 KB Output is correct
13 Correct 414 ms 56252 KB Output is correct
14 Correct 2 ms 1364 KB Output is correct
15 Correct 243 ms 56476 KB Output is correct
16 Correct 109 ms 56640 KB Output is correct
17 Correct 99 ms 56200 KB Output is correct
18 Correct 103 ms 56232 KB Output is correct
19 Correct 114 ms 56348 KB Output is correct
20 Correct 126 ms 56092 KB Output is correct
21 Correct 109 ms 56236 KB Output is correct
22 Execution timed out 7013 ms 56364 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 1364 KB Output is correct
2 Correct 107 ms 55748 KB Output is correct
3 Correct 117 ms 56284 KB Output is correct
4 Correct 106 ms 56224 KB Output is correct
5 Correct 98 ms 56108 KB Output is correct
6 Correct 110 ms 56368 KB Output is correct
7 Correct 121 ms 56352 KB Output is correct
8 Correct 102 ms 56032 KB Output is correct
9 Correct 96 ms 55984 KB Output is correct
10 Correct 100 ms 55932 KB Output is correct
11 Correct 128 ms 56340 KB Output is correct
12 Correct 417 ms 56412 KB Output is correct
13 Correct 414 ms 56252 KB Output is correct
14 Correct 2 ms 1364 KB Output is correct
15 Correct 243 ms 56476 KB Output is correct
16 Correct 109 ms 56640 KB Output is correct
17 Correct 99 ms 56200 KB Output is correct
18 Correct 103 ms 56232 KB Output is correct
19 Correct 114 ms 56348 KB Output is correct
20 Correct 126 ms 56092 KB Output is correct
21 Correct 109 ms 56236 KB Output is correct
22 Execution timed out 7013 ms 56364 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1364 KB Output is correct
2 Correct 693 ms 435740 KB Output is correct
3 Correct 626 ms 437236 KB Output is correct
4 Correct 652 ms 437220 KB Output is correct
5 Correct 669 ms 437372 KB Output is correct
6 Correct 757 ms 437440 KB Output is correct
7 Correct 624 ms 436944 KB Output is correct
8 Correct 2 ms 1364 KB Output is correct
9 Correct 107 ms 55748 KB Output is correct
10 Correct 117 ms 56284 KB Output is correct
11 Correct 106 ms 56224 KB Output is correct
12 Correct 98 ms 56108 KB Output is correct
13 Correct 110 ms 56368 KB Output is correct
14 Correct 121 ms 56352 KB Output is correct
15 Correct 102 ms 56032 KB Output is correct
16 Correct 96 ms 55984 KB Output is correct
17 Correct 100 ms 55932 KB Output is correct
18 Correct 128 ms 56340 KB Output is correct
19 Correct 417 ms 56412 KB Output is correct
20 Correct 414 ms 56252 KB Output is correct
21 Correct 2 ms 1364 KB Output is correct
22 Correct 243 ms 56476 KB Output is correct
23 Correct 109 ms 56640 KB Output is correct
24 Correct 99 ms 56200 KB Output is correct
25 Correct 103 ms 56232 KB Output is correct
26 Correct 114 ms 56348 KB Output is correct
27 Correct 126 ms 56092 KB Output is correct
28 Correct 109 ms 56236 KB Output is correct
29 Execution timed out 7013 ms 56364 KB Time limit exceeded
30 Halted 0 ms 0 KB -