oj.uz

Submission #618956

# Submission time Handle Problem Language Result Execution time Memory
618956 2022-08-02T08:37:06 Z happypotato Dungeons Game (IOI21_dungeons) C++17
36 / 100
 7000 ms 91484 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
const int mxN = 5e4 + 1;
vector<int> s, p, w, l;
int n;
int st;
// st34 initialize
int liftpar[6][mxN][25];
ll int liftsum[6][mxN][25];
vector<int> diffs = {0};
void ComputeLift() {
    for (int i = 0; i < int(diffs.size()); i++) {
        for (int u = 0; u < n; u++) {
            if (s[u] <= diffs[i]) {
                liftpar[i][u][0] = w[u];
                liftsum[i][u][0] = s[u];
            } else {
                liftpar[i][u][0] = l[u];
                liftsum[i][u][0] = p[u];
            }
        }
        for (int dep = 1; dep < 25; dep++) {
            for (int u = 0; u < n; u++) {
                if (liftpar[i][u][dep - 1] == n) {
                    liftpar[i][u][dep] = n;
                    liftsum[i][u][dep] = liftsum[i][u][dep - 1];
                } else {
                    liftpar[i][u][dep] = liftpar[i][liftpar[i][u][dep - 1]][dep - 1];
                    liftsum[i][u][dep] = liftsum[i][u][dep - 1] + liftsum[i][liftpar[i][u][dep - 1]][dep - 1];
                }
            }
        }
    }
}
void st34init() {
    for (int i = 0; i < n; i++) {
        bool appear = false;
        for (int &x : diffs) {
            appear |= (x == s[i]);
        }
        if (!appear) diffs.pb(s[i]);
    }
    sort(diffs.begin(), diffs.end());
    ComputeLift();
}
void init(int on, vector<int> os, vector<int> op, vector<int> ow, vector<int> ol) {
    n = on;
    s = os; p = op; w = ow; l = ol;
    bool isst2 = true;
    for (int i = 0; i < n; i++) {
        isst2 &= (s[i] == p[i]);
    }
    if (isst2) {
        st = 2;
        return;
    } else if (n > 50000) {
        st = 6;
        return;
    }
    set<int> dists;
    for (int i = 0; i < n; i++) {
        dists.insert(s[i]);
        if (dists.size() > 5) break;
    }
    if (dists.size() <= 5) {
        st = 4;
        st34init();
        return;
    }
    // 1 and 5 is ???
    st = 1;
    return;
}
ll int st1(int x, ll int z) {
    while (x != n) {
        if (z >= s[x]) {
            z += s[x];
            x = w[x];
        } else {
            z += p[x];
            x = l[x];
        }
    }
    return z;
}
ll int st2(int x, ll int z) {
    return 0;
}
ll int st34(int x, ll int z) {
    for (int i = 0; i < int(diffs.size()); i++) {
        ll int tar = (i == int(diffs.size()) - 1 ? 1e18 : diffs[i + 1]);
        if (z >= tar) continue;
        for (int dep = 24; dep >= 0; dep--) {
            if (z + liftsum[i][x][dep] < tar) {
                z += liftsum[i][x][dep];
                x = liftpar[i][x][dep];
                if (x == n) return z;
            }
        }
        z += liftsum[i][x][0];
        x = liftpar[i][x][0];
        if (x == n) return z;
    }
    return -1;
}
long long simulate(int x, int z) {
    if (st == 1) return st1(x, z);
    if (st == 2) return st2(x, z);
    if (st == 3 || st == 4) return st34(x, z);
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 17 ms 2644 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 16 ms 2644 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 90 ms 32800 KB Output is correct
3 Correct 90 ms 32832 KB Output is correct
4 Correct 87 ms 32796 KB Output is correct
5 Correct 76 ms 32720 KB Output is correct
6 Correct 109 ms 32712 KB Output is correct
7 Correct 111 ms 32712 KB Output is correct
8 Correct 96 ms 32804 KB Output is correct
9 Correct 103 ms 32804 KB Output is correct
10 Correct 123 ms 32712 KB Output is correct
11 Correct 99 ms 32708 KB Output is correct
12 Correct 163 ms 32712 KB Output is correct
13 Correct 138 ms 32752 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 90 ms 32800 KB Output is correct
3 Correct 90 ms 32832 KB Output is correct
4 Correct 87 ms 32796 KB Output is correct
5 Correct 76 ms 32720 KB Output is correct
6 Correct 109 ms 32712 KB Output is correct
7 Correct 111 ms 32712 KB Output is correct
8 Correct 96 ms 32804 KB Output is correct
9 Correct 103 ms 32804 KB Output is correct
10 Correct 123 ms 32712 KB Output is correct
11 Correct 99 ms 32708 KB Output is correct
12 Correct 163 ms 32712 KB Output is correct
13 Correct 138 ms 32752 KB Output is correct
14 Correct 2 ms 1892 KB Output is correct
15 Correct 161 ms 62072 KB Output is correct
16 Correct 177 ms 76744 KB Output is correct
17 Correct 215 ms 91480 KB Output is correct
18 Correct 230 ms 91424 KB Output is correct
19 Correct 192 ms 91484 KB Output is correct
20 Correct 184 ms 62088 KB Output is correct
21 Correct 229 ms 76836 KB Output is correct
22 Correct 153 ms 47428 KB Output is correct
23 Correct 270 ms 76740 KB Output is correct
24 Correct 282 ms 62152 KB Output is correct

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 980 KB Output is correct
2 Correct 90 ms 32800 KB Output is correct
3 Correct 90 ms 32832 KB Output is correct
4 Correct 87 ms 32796 KB Output is correct
5 Correct 76 ms 32720 KB Output is correct
6 Correct 109 ms 32712 KB Output is correct
7 Correct 111 ms 32712 KB Output is correct
8 Correct 96 ms 32804 KB Output is correct
9 Correct 103 ms 32804 KB Output is correct
10 Correct 123 ms 32712 KB Output is correct
11 Correct 99 ms 32708 KB Output is correct
12 Correct 163 ms 32712 KB Output is correct
13 Correct 138 ms 32752 KB Output is correct
14 Correct 2 ms 1892 KB Output is correct
15 Correct 161 ms 62072 KB Output is correct
16 Correct 177 ms 76744 KB Output is correct
17 Correct 215 ms 91480 KB Output is correct
18 Correct 230 ms 91424 KB Output is correct
19 Correct 192 ms 91484 KB Output is correct
20 Correct 184 ms 62088 KB Output is correct
21 Correct 229 ms 76836 KB Output is correct
22 Correct 153 ms 47428 KB Output is correct
23 Correct 270 ms 76740 KB Output is correct
24 Correct 282 ms 62152 KB Output is correct
25 Correct 18 ms 2656 KB Output is correct
26 Correct 51 ms 5056 KB Output is correct
27 Correct 43 ms 4536 KB Output is correct
28 Correct 373 ms 4516 KB Output is correct
29 Correct 45 ms 4940 KB Output is correct
30 Execution timed out 7085 ms 4692 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -