Submission #950729

#	Time	Username	Problem	Language	Result	Execution time	Memory
950729		Nhoksocqt1	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	3423 ms	2024656 KiB

dungeons

#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 / 11
• Subtask 2: 26 / 26
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 27 / 27
• Subtask 6: 11 / 11