oj.uz

Submission #950694

# Submission time Handle Problem Language Result Execution time Memory
950694 2024-03-20T15:21:47 Z Nhoksocqt1 Dungeons Game (IOI21_dungeons) C++17
39 / 100
 5645 ms 735676 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;
const int MAXM = 50004;

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

ll Psums[MAXN][24], Psump[MAXN][24], Psum[24][MAXM][24];
int Pl[MAXN][24], Ps[24][MAXM][24], P[24][MAXM][24];
int Pw[MAXN][24], Psa[MAXN][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] = Pl[nArr][0] = -1;
    for (int i = nArr - 1; i >= 0; --i) {
        Pw[i][0] = dungeons[i].w;
        Pl[i][0] = dungeons[i].l;
        depth[i] = depth[Pw[i][0]] + 1;
        Psa[i][0] = Psums[i][0] = dungeons[i].s;
        Psump[i][0] = dungeons[i].p;
    }

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

            if(Pw[i][j - 1] == -1) {
                Pw[i][j] = -1;
            } else {
                Pw[i][j] = Pw[Pw[i][j - 1]][j - 1];
                Psa[i][j] = max(Psa[i][j - 1], Psa[Pw[i][j - 1]][j - 1]);
                Psums[i][j] = Psums[i][j - 1] + Psums[Pw[i][j - 1]][j - 1];
            }
        }
    }

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

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

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;
}

// z < s[i] do not exceed log2(max(s[i])) time
ll sub2(int x, ll z) {
    while(x < nArr) {
        for (int i = 31 - __builtin_clz(depth[x]); i >= 0; --i) {
            if(Pw[x][i] != -1 && Psa[x][i] <= z) {
                z += Psums[x][i];
                x = Pw[x][i];
            }
        }

        if(x < nArr && z < dungeons[x].s) {
            z += dungeons[x].p;
            x = dungeons[x].l;
        }
    }

    return z;
}

// lose all until z >= s[.]
ll sub3(int x, ll z) {
    for (int i = 23; i >= 0; --i) {
        if(Pl[x][i] != -1 && z + Psump[x][i] < dungeons[0].s) {
            z += Psump[x][i];
            x = Pl[x][i];
        }
    }

    if(x < nArr && z < dungeons[0].s) {
        z += Psump[x][0];
        x = Pl[x][0];
    }

    if(x < nArr) {
        assert(z >= dungeons[0].s);
        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 sub5(int x, ll z) {
    for (int k = 0; k < 24; ++k) {
        if(z >= (1 << (k + 1)))
            continue;

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

        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[k][x][0];
            x = P[k][x][0];
        }
    }

    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) {
    if(check_sub2)
        return sub2(x, z);

    if(check_sub3)
        return sub3(x, z);

    if(nArr <= 50000)
        return sub5(x, z);

    return sub1(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];

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

    return 0;
}

#endif // Nhoksocqt1

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 160336 KB Output is correct
2 Correct 17 ms 160348 KB Output is correct
3 Correct 26 ms 181084 KB Output is correct
4 Incorrect 391 ms 498524 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 172636 KB Output is correct
2 Correct 5421 ms 735500 KB Output is correct
3 Correct 5109 ms 735508 KB Output is correct
4 Correct 5075 ms 735500 KB Output is correct
5 Correct 4698 ms 735500 KB Output is correct
6 Correct 5645 ms 735332 KB Output is correct
7 Correct 5232 ms 735676 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 172636 KB Output is correct
2 Correct 427 ms 499288 KB Output is correct
3 Correct 444 ms 499412 KB Output is correct
4 Correct 441 ms 499552 KB Output is correct
5 Correct 426 ms 499540 KB Output is correct
6 Correct 394 ms 499716 KB Output is correct
7 Correct 409 ms 499304 KB Output is correct
8 Correct 362 ms 499540 KB Output is correct
9 Correct 246 ms 499536 KB Output is correct
10 Correct 341 ms 499480 KB Output is correct
11 Correct 498 ms 499536 KB Output is correct
12 Correct 665 ms 499440 KB Output is correct
13 Correct 473 ms 499512 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 172636 KB Output is correct
2 Correct 427 ms 499288 KB Output is correct
3 Correct 444 ms 499412 KB Output is correct
4 Correct 441 ms 499552 KB Output is correct
5 Correct 426 ms 499540 KB Output is correct
6 Correct 394 ms 499716 KB Output is correct
7 Correct 409 ms 499304 KB Output is correct
8 Correct 362 ms 499540 KB Output is correct
9 Correct 246 ms 499536 KB Output is correct
10 Correct 341 ms 499480 KB Output is correct
11 Correct 498 ms 499536 KB Output is correct
12 Correct 665 ms 499440 KB Output is correct
13 Correct 473 ms 499512 KB Output is correct
14 Correct 21 ms 172636 KB Output is correct
15 Incorrect 416 ms 499444 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 172636 KB Output is correct
2 Correct 427 ms 499288 KB Output is correct
3 Correct 444 ms 499412 KB Output is correct
4 Correct 441 ms 499552 KB Output is correct
5 Correct 426 ms 499540 KB Output is correct
6 Correct 394 ms 499716 KB Output is correct
7 Correct 409 ms 499304 KB Output is correct
8 Correct 362 ms 499540 KB Output is correct
9 Correct 246 ms 499536 KB Output is correct
10 Correct 341 ms 499480 KB Output is correct
11 Correct 498 ms 499536 KB Output is correct
12 Correct 665 ms 499440 KB Output is correct
13 Correct 473 ms 499512 KB Output is correct
14 Correct 21 ms 172636 KB Output is correct
15 Incorrect 416 ms 499444 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 172636 KB Output is correct
2 Correct 5421 ms 735500 KB Output is correct
3 Correct 5109 ms 735508 KB Output is correct
4 Correct 5075 ms 735500 KB Output is correct
5 Correct 4698 ms 735500 KB Output is correct
6 Correct 5645 ms 735332 KB Output is correct
7 Correct 5232 ms 735676 KB Output is correct
8 Correct 21 ms 172636 KB Output is correct
9 Correct 427 ms 499288 KB Output is correct
10 Correct 444 ms 499412 KB Output is correct
11 Correct 441 ms 499552 KB Output is correct
12 Correct 426 ms 499540 KB Output is correct
13 Correct 394 ms 499716 KB Output is correct
14 Correct 409 ms 499304 KB Output is correct
15 Correct 362 ms 499540 KB Output is correct
16 Correct 246 ms 499536 KB Output is correct
17 Correct 341 ms 499480 KB Output is correct
18 Correct 498 ms 499536 KB Output is correct
19 Correct 665 ms 499440 KB Output is correct
20 Correct 473 ms 499512 KB Output is correct
21 Correct 21 ms 172636 KB Output is correct
22 Incorrect 416 ms 499444 KB Output isn't correct
23 Halted 0 ms 0 KB -