oj.uz

Submission #950714

# Submission time Handle Problem Language Result Execution time Memory
950714 2024-03-20T15:36:14 Z Nhoksocqt1 Dungeons Game (IOI21_dungeons) C++17
89 / 100
 7000 ms 614128 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], Ps[24][MAXM][24], Psum[24][MAXM][24];
int Pl[MAXN][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];
            }
        }
    }

    if(nArr <= 50000) {
        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 - 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];
        //_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 64 ms 160336 KB Output is correct
2 Correct 18 ms 160348 KB Output is correct
3 Correct 39 ms 187216 KB Output is correct
4 Correct 484 ms 611532 KB Output is correct
5 Correct 24 ms 187228 KB Output is correct
6 Correct 329 ms 611540 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 172636 KB Output is correct
2 Correct 459 ms 287832 KB Output is correct
3 Correct 452 ms 288036 KB Output is correct
4 Correct 428 ms 287812 KB Output is correct
5 Correct 376 ms 287812 KB Output is correct
6 Correct 474 ms 288084 KB Output is correct
7 Correct 493 ms 288044 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 172632 KB Output is correct
2 Correct 431 ms 612348 KB Output is correct
3 Correct 428 ms 612512 KB Output is correct
4 Correct 395 ms 612320 KB Output is correct
5 Correct 363 ms 612312 KB Output is correct
6 Correct 465 ms 612608 KB Output is correct
7 Correct 443 ms 612176 KB Output is correct
8 Correct 363 ms 612384 KB Output is correct
9 Correct 277 ms 612404 KB Output is correct
10 Correct 412 ms 612364 KB Output is correct
11 Correct 559 ms 612404 KB Output is correct
12 Correct 751 ms 612176 KB Output is correct
13 Correct 505 ms 612572 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 172632 KB Output is correct
2 Correct 431 ms 612348 KB Output is correct
3 Correct 428 ms 612512 KB Output is correct
4 Correct 395 ms 612320 KB Output is correct
5 Correct 363 ms 612312 KB Output is correct
6 Correct 465 ms 612608 KB Output is correct
7 Correct 443 ms 612176 KB Output is correct
8 Correct 363 ms 612384 KB Output is correct
9 Correct 277 ms 612404 KB Output is correct
10 Correct 412 ms 612364 KB Output is correct
11 Correct 559 ms 612404 KB Output is correct
12 Correct 751 ms 612176 KB Output is correct
13 Correct 505 ms 612572 KB Output is correct
14 Correct 21 ms 172632 KB Output is correct
15 Correct 453 ms 612516 KB Output is correct
16 Correct 479 ms 612176 KB Output is correct
17 Correct 561 ms 612328 KB Output is correct
18 Correct 593 ms 612232 KB Output is correct
19 Correct 655 ms 612180 KB Output is correct
20 Correct 705 ms 612240 KB Output is correct
21 Correct 828 ms 612180 KB Output is correct
22 Correct 951 ms 612180 KB Output is correct
23 Correct 1557 ms 612348 KB Output is correct
24 Correct 1634 ms 613620 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 172632 KB Output is correct
2 Correct 431 ms 612348 KB Output is correct
3 Correct 428 ms 612512 KB Output is correct
4 Correct 395 ms 612320 KB Output is correct
5 Correct 363 ms 612312 KB Output is correct
6 Correct 465 ms 612608 KB Output is correct
7 Correct 443 ms 612176 KB Output is correct
8 Correct 363 ms 612384 KB Output is correct
9 Correct 277 ms 612404 KB Output is correct
10 Correct 412 ms 612364 KB Output is correct
11 Correct 559 ms 612404 KB Output is correct
12 Correct 751 ms 612176 KB Output is correct
13 Correct 505 ms 612572 KB Output is correct
14 Correct 21 ms 172632 KB Output is correct
15 Correct 453 ms 612516 KB Output is correct
16 Correct 479 ms 612176 KB Output is correct
17 Correct 561 ms 612328 KB Output is correct
18 Correct 593 ms 612232 KB Output is correct
19 Correct 655 ms 612180 KB Output is correct
20 Correct 705 ms 612240 KB Output is correct
21 Correct 828 ms 612180 KB Output is correct
22 Correct 951 ms 612180 KB Output is correct
23 Correct 1557 ms 612348 KB Output is correct
24 Correct 1634 ms 613620 KB Output is correct
25 Correct 456 ms 612872 KB Output is correct
26 Correct 481 ms 614128 KB Output is correct
27 Correct 460 ms 613392 KB Output is correct
28 Correct 421 ms 613580 KB Output is correct
29 Correct 517 ms 613868 KB Output is correct
30 Correct 794 ms 613656 KB Output is correct
31 Correct 848 ms 613356 KB Output is correct
32 Correct 1041 ms 613460 KB Output is correct
33 Correct 880 ms 613596 KB Output is correct
34 Correct 1477 ms 613596 KB Output is correct
35 Correct 923 ms 613504 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 172636 KB Output is correct
2 Correct 459 ms 287832 KB Output is correct
3 Correct 452 ms 288036 KB Output is correct
4 Correct 428 ms 287812 KB Output is correct
5 Correct 376 ms 287812 KB Output is correct
6 Correct 474 ms 288084 KB Output is correct
7 Correct 493 ms 288044 KB Output is correct
8 Correct 21 ms 172632 KB Output is correct
9 Correct 431 ms 612348 KB Output is correct
10 Correct 428 ms 612512 KB Output is correct
11 Correct 395 ms 612320 KB Output is correct
12 Correct 363 ms 612312 KB Output is correct
13 Correct 465 ms 612608 KB Output is correct
14 Correct 443 ms 612176 KB Output is correct
15 Correct 363 ms 612384 KB Output is correct
16 Correct 277 ms 612404 KB Output is correct
17 Correct 412 ms 612364 KB Output is correct
18 Correct 559 ms 612404 KB Output is correct
19 Correct 751 ms 612176 KB Output is correct
20 Correct 505 ms 612572 KB Output is correct
21 Correct 21 ms 172632 KB Output is correct
22 Correct 453 ms 612516 KB Output is correct
23 Correct 479 ms 612176 KB Output is correct
24 Correct 561 ms 612328 KB Output is correct
25 Correct 593 ms 612232 KB Output is correct
26 Correct 655 ms 612180 KB Output is correct
27 Correct 705 ms 612240 KB Output is correct
28 Correct 828 ms 612180 KB Output is correct
29 Correct 951 ms 612180 KB Output is correct
30 Correct 1557 ms 612348 KB Output is correct
31 Correct 1634 ms 613620 KB Output is correct
32 Correct 456 ms 612872 KB Output is correct
33 Correct 481 ms 614128 KB Output is correct
34 Correct 460 ms 613392 KB Output is correct
35 Correct 421 ms 613580 KB Output is correct
36 Correct 517 ms 613868 KB Output is correct
37 Correct 794 ms 613656 KB Output is correct
38 Correct 848 ms 613356 KB Output is correct
39 Correct 1041 ms 613460 KB Output is correct
40 Correct 880 ms 613596 KB Output is correct
41 Correct 1477 ms 613596 KB Output is correct
42 Correct 923 ms 613504 KB Output is correct
43 Correct 17 ms 160348 KB Output is correct
44 Correct 21 ms 172884 KB Output is correct
45 Correct 386 ms 299456 KB Output is correct
46 Correct 407 ms 295040 KB Output is correct
47 Correct 4453 ms 295472 KB Output is correct
48 Execution timed out 7035 ms 297412 KB Time limit exceeded
49 Halted 0 ms 0 KB -