oj.uz

Submission #950729

# Submission time Handle Problem Language Result Execution time Memory
950729 2024-03-20T15:51:04 Z Nhoksocqt1 Dungeons Game (IOI21_dungeons) C++17
100 / 100
 3423 ms 2024656 KB 
#include<bits/stdc++.h>
using namespace std;

#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;

template<class X, class Y>
	inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
	inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
    return uniform_int_distribution<int>(l, r)(rng);
}

const int MAXN = 400005;

struct Dungeon {
    int s, p, w, l;
} dungeons[MAXN];

ll Psums[MAXN][24], Psum[300][MAXN];
int P[300][MAXN], Ps[300][MAXN], Pw[MAXN][24];
int id[24][24], depth[MAXN], nArr;
bool check_sub2, check_sub3;

void init(int _N, vector<int> _S, vector<int> _P, vector<int> _W, vector<int> _L) {
    nArr = _N;
    check_sub2 = check_sub3 = 1;
    for (int i = 0; i < nArr; ++i) {
        dungeons[i] = {_S[i], _P[i], _W[i], _L[i]};
        check_sub2 &= (dungeons[i].s == dungeons[i].p);
        check_sub3 &= (dungeons[i].s == dungeons[0].s);
    }

    depth[nArr] = 0;
    Pw[nArr][0] = -1;
    for (int i = nArr - 1; i >= 0; --i) {
        Pw[i][0] = dungeons[i].w;
        depth[i] = depth[Pw[i][0]] + 1;
        Psums[i][0] = dungeons[i].s;
    }

    for (int j = 1; j < 24; ++j) {
        for (int i = 0; i <= nArr; ++i) {
            if(Pw[i][j - 1] == -1) {
                Pw[i][j] = -1;
            } else {
                Pw[i][j] = Pw[Pw[i][j - 1]][j - 1];
                Psums[i][j] = Psums[i][j - 1] + Psums[Pw[i][j - 1]][j - 1];
            }
        }
    }

    int cnt(0);
    for (int i = 0; i < 24; ++i) {
        for (int j = 0; j <= i; ++j)
            id[i][j] = cnt++;
    }

    for (int k = 0; k < 24; ++k) {
        P[id[k][0]][nArr] = -1;
        for (int i = nArr - 1; i >= 0; --i) {
            P[id[k][0]][i] = (dungeons[i].s > (1 << k)) ? dungeons[i].l : dungeons[i].w;
            Psum[id[k][0]][i] = (dungeons[i].s > (1 << k)) ? dungeons[i].p : dungeons[i].s;
            Ps[id[k][0]][i] = (dungeons[i].s > (1 << k)) ? dungeons[i].s : 1e9;
        }

        for (int j = 1; j <= k; ++j) {
            for (int i = 0; i <= nArr; ++i) {
                if(P[id[k][j - 1]][i] == -1) {
                    P[id[k][j]][i] = -1;
                } else {
                    P[id[k][j]][i] = P[id[k][j - 1]][P[id[k][j - 1]][i]];
                    Ps[id[k][j]][i] = max(0LL, min(ll(Ps[id[k][j - 1]][i]), Ps[id[k][j - 1]][P[id[k][j - 1]][i]] - Psum[id[k][j - 1]][i]));
                    Psum[id[k][j]][i] = Psum[id[k][j - 1]][i] + Psum[id[k][j - 1]][P[id[k][j - 1]][i]];
                }
            }
        }
    }
}

ll sub1(int x, ll z) {
    while(x < nArr) {
        if(z >= dungeons[x].s) {
            z += dungeons[x].s;
            x = dungeons[x].w;
        } else {
            z += dungeons[x].p;
            x = dungeons[x].l;
        }
    }

    return z;
}

ll magicFunc(int x, ll z) {
    for (int k = 0; k < 24; ++k) {
        if(z >= (1 << (k + 1)))
            continue;

        for (int j = k; j >= 0; --j) {
            if(P[id[k][j]][x] != -1 && (Ps[id[k][j]][x] >= 1e9 || Ps[id[k][j]][x] > z) && z + Psum[id[k][j]][x] < (1 << (k + 1))) {
                z += Psum[id[k][j]][x];
                x = P[id[k][j]][x];
            }
        }

        if(x < nArr && z < (1 << (k + 1)) && z >= dungeons[x].s) {
            z += dungeons[x].s;
            x = dungeons[x].w;
        }

        if(x < nArr && z < (1 << (k + 1))) {
            z += Psum[id[k][0]][x];
            x = P[id[k][0]][x];
        }
    }

    if(x < nArr) {
        for (int i = 31 - __builtin_clz(depth[x]); i >= 0; --i) {
            if(Pw[x][i] != -1) {
                z += Psums[x][i];
                x = Pw[x][i];
            }
        }
    }

    return z;
}

ll simulate(int x, int z) {
    return magicFunc(x, z);
}

#ifdef Nhoksocqt1

int main(void) {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    #define TASK "dungeons"
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    vector<int> _S, _P, _W, _L;
    int nArr, numQuery;
    cin >> nArr >> numQuery;

    _S.resize(nArr), _P.resize(nArr), _W.resize(nArr), _L.resize(nArr);
    for (int i = 0; i < nArr; ++i) {
        cin >> _S[i] >> _P[i] >> _W[i] >> _L[i];
        //_S[i] = Random(1, 1e5), _P[i] = Random(1, 1e5), _W[i] = Random(i + 1, nArr), _L[i] = Random(0, nArr); cout << _S[i] << ' ' << _P[i] << ' ' << _W[i] << ' ' << _L[i] << '\n';
    }

    init(nArr, _S, _P, _W, _L);
    for (int t = 0; t < numQuery; ++t) {
        int x, z;
        cin >> x >> z;
        //x = Random(0, nArr - 1), z = Random(1, 1e5);
        cout << "ANSWER FOR SIMULATE(" << x << "," << z << ") = " << simulate(x, z) << '\n';
    }

    return 0;
}

#endif // Nhoksocqt1

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 556132 KB Output is correct
2 Correct 57 ms 556324 KB Output is correct
3 Correct 59 ms 558384 KB Output is correct
4 Correct 138 ms 635348 KB Output is correct
5 Correct 62 ms 563536 KB Output is correct
6 Correct 137 ms 642644 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 565844 KB Output is correct
2 Correct 2411 ms 2012988 KB Output is correct
3 Correct 1380 ms 1995040 KB Output is correct
4 Correct 1654 ms 1948676 KB Output is correct
5 Correct 1163 ms 1710044 KB Output is correct
6 Correct 3423 ms 2016732 KB Output is correct
7 Correct 3056 ms 2015732 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 632064 KB Output is correct
2 Correct 261 ms 762812 KB Output is correct
3 Correct 314 ms 777020 KB Output is correct
4 Correct 233 ms 760144 KB Output is correct
5 Correct 246 ms 756936 KB Output is correct
6 Correct 959 ms 763028 KB Output is correct
7 Correct 1002 ms 773048 KB Output is correct
8 Correct 927 ms 760296 KB Output is correct
9 Correct 193 ms 681232 KB Output is correct
10 Correct 704 ms 758600 KB Output is correct
11 Correct 987 ms 761228 KB Output is correct
12 Correct 2656 ms 783900 KB Output is correct
13 Correct 2754 ms 782036 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 632064 KB Output is correct
2 Correct 261 ms 762812 KB Output is correct
3 Correct 314 ms 777020 KB Output is correct
4 Correct 233 ms 760144 KB Output is correct
5 Correct 246 ms 756936 KB Output is correct
6 Correct 959 ms 763028 KB Output is correct
7 Correct 1002 ms 773048 KB Output is correct
8 Correct 927 ms 760296 KB Output is correct
9 Correct 193 ms 681232 KB Output is correct
10 Correct 704 ms 758600 KB Output is correct
11 Correct 987 ms 761228 KB Output is correct
12 Correct 2656 ms 783900 KB Output is correct
13 Correct 2754 ms 782036 KB Output is correct
14 Correct 67 ms 633172 KB Output is correct
15 Correct 259 ms 783956 KB Output is correct
16 Correct 278 ms 770268 KB Output is correct
17 Correct 423 ms 764060 KB Output is correct
18 Correct 443 ms 774932 KB Output is correct
19 Correct 967 ms 778652 KB Output is correct
20 Correct 953 ms 766268 KB Output is correct
21 Correct 1236 ms 776920 KB Output is correct
22 Correct 954 ms 748080 KB Output is correct
23 Correct 1319 ms 748680 KB Output is correct
24 Correct 1753 ms 773244 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 632064 KB Output is correct
2 Correct 261 ms 762812 KB Output is correct
3 Correct 314 ms 777020 KB Output is correct
4 Correct 233 ms 760144 KB Output is correct
5 Correct 246 ms 756936 KB Output is correct
6 Correct 959 ms 763028 KB Output is correct
7 Correct 1002 ms 773048 KB Output is correct
8 Correct 927 ms 760296 KB Output is correct
9 Correct 193 ms 681232 KB Output is correct
10 Correct 704 ms 758600 KB Output is correct
11 Correct 987 ms 761228 KB Output is correct
12 Correct 2656 ms 783900 KB Output is correct
13 Correct 2754 ms 782036 KB Output is correct
14 Correct 67 ms 633172 KB Output is correct
15 Correct 259 ms 783956 KB Output is correct
16 Correct 278 ms 770268 KB Output is correct
17 Correct 423 ms 764060 KB Output is correct
18 Correct 443 ms 774932 KB Output is correct
19 Correct 967 ms 778652 KB Output is correct
20 Correct 953 ms 766268 KB Output is correct
21 Correct 1236 ms 776920 KB Output is correct
22 Correct 954 ms 748080 KB Output is correct
23 Correct 1319 ms 748680 KB Output is correct
24 Correct 1753 ms 773244 KB Output is correct
25 Correct 191 ms 801116 KB Output is correct
26 Correct 312 ms 824140 KB Output is correct
27 Correct 241 ms 823636 KB Output is correct
28 Correct 251 ms 832132 KB Output is correct
29 Correct 333 ms 832620 KB Output is correct
30 Correct 820 ms 825944 KB Output is correct
31 Correct 1035 ms 827928 KB Output is correct
32 Correct 1157 ms 798300 KB Output is correct
33 Correct 1012 ms 834128 KB Output is correct
34 Correct 1639 ms 826424 KB Output is correct
35 Correct 1033 ms 833920 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 565844 KB Output is correct
2 Correct 2411 ms 2012988 KB Output is correct
3 Correct 1380 ms 1995040 KB Output is correct
4 Correct 1654 ms 1948676 KB Output is correct
5 Correct 1163 ms 1710044 KB Output is correct
6 Correct 3423 ms 2016732 KB Output is correct
7 Correct 3056 ms 2015732 KB Output is correct
8 Correct 66 ms 632064 KB Output is correct
9 Correct 261 ms 762812 KB Output is correct
10 Correct 314 ms 777020 KB Output is correct
11 Correct 233 ms 760144 KB Output is correct
12 Correct 246 ms 756936 KB Output is correct
13 Correct 959 ms 763028 KB Output is correct
14 Correct 1002 ms 773048 KB Output is correct
15 Correct 927 ms 760296 KB Output is correct
16 Correct 193 ms 681232 KB Output is correct
17 Correct 704 ms 758600 KB Output is correct
18 Correct 987 ms 761228 KB Output is correct
19 Correct 2656 ms 783900 KB Output is correct
20 Correct 2754 ms 782036 KB Output is correct
21 Correct 67 ms 633172 KB Output is correct
22 Correct 259 ms 783956 KB Output is correct
23 Correct 278 ms 770268 KB Output is correct
24 Correct 423 ms 764060 KB Output is correct
25 Correct 443 ms 774932 KB Output is correct
26 Correct 967 ms 778652 KB Output is correct
27 Correct 953 ms 766268 KB Output is correct
28 Correct 1236 ms 776920 KB Output is correct
29 Correct 954 ms 748080 KB Output is correct
30 Correct 1319 ms 748680 KB Output is correct
31 Correct 1753 ms 773244 KB Output is correct
32 Correct 191 ms 801116 KB Output is correct
33 Correct 312 ms 824140 KB Output is correct
34 Correct 241 ms 823636 KB Output is correct
35 Correct 251 ms 832132 KB Output is correct
36 Correct 333 ms 832620 KB Output is correct
37 Correct 820 ms 825944 KB Output is correct
38 Correct 1035 ms 827928 KB Output is correct
39 Correct 1157 ms 798300 KB Output is correct
40 Correct 1012 ms 834128 KB Output is correct
41 Correct 1639 ms 826424 KB Output is correct
42 Correct 1033 ms 833920 KB Output is correct
43 Correct 69 ms 685908 KB Output is correct
44 Correct 76 ms 698140 KB Output is correct
45 Correct 1574 ms 1959008 KB Output is correct
46 Correct 1197 ms 1935180 KB Output is correct
47 Correct 1215 ms 2017348 KB Output is correct
48 Correct 1301 ms 2018056 KB Output is correct
49 Correct 1769 ms 2024656 KB Output is correct
50 Correct 2275 ms 2022192 KB Output is correct
51 Correct 1384 ms 2022360 KB Output is correct
52 Correct 2448 ms 1995092 KB Output is correct
53 Correct 3059 ms 1788688 KB Output is correct
54 Correct 2225 ms 2022236 KB Output is correct
55 Correct 3089 ms 1977196 KB Output is correct
56 Correct 2969 ms 2021940 KB Output is correct
57 Correct 2805 ms 2021692 KB Output is correct
58 Correct 2782 ms 2021956 KB Output is correct
59 Correct 2708 ms 2022084 KB Output is correct
60 Correct 2761 ms 2021448 KB Output is correct
61 Correct 2470 ms 2021084 KB Output is correct