oj.uz

답안 #950653

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
950653 2024-03-20T14:24:51 Z Nhoksocqt1 던전 (IOI21_dungeons) C++17
37 / 100
 7000 ms 149072 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 Psum[MAXN][19];
int P[MAXN][19], Ps[MAXN][19], depth[MAXN], nArr;
bool check_sub2;

void init(int _N, vector<int> _S, vector<int> _P, vector<int> _W, vector<int> _L) {
    nArr = _N;
    check_sub2 = 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);
    }

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

    for (int j = 1; (1 << j) <= nArr + 1; ++j) {
        for (int i = 0; i <= nArr; ++i) {
            if(P[i][j - 1] == -1) {
                P[i][j] = -1;
            } else {
                P[i][j] = P[P[i][j - 1]][j - 1];
                Ps[i][j] = max(Ps[i][j - 1], Ps[P[i][j - 1]][j - 1]);
                Psum[i][j] = Psum[i][j - 1] + Psum[P[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(P[x][i] != -1 && Ps[x][i] <= z) {
                z += Psum[x][i];
                x = P[x][i];
            }
        }

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

    return z;
}

ll simulate(int x, int z) {
    if(check_sub2)
        return sub2(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
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 21 ms 27852 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 21 ms 27484 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 294 ms 147632 KB Output is correct
3 Correct 302 ms 147540 KB Output is correct
4 Correct 305 ms 149072 KB Output is correct
5 Correct 233 ms 148924 KB Output is correct
6 Correct 309 ms 147284 KB Output is correct
7 Correct 350 ms 145676 KB Output is correct

Subtask #3
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 39 ms 29020 KB Output is correct
3 Correct 2567 ms 29112 KB Output is correct
4 Correct 3006 ms 28560 KB Output is correct
5 Correct 2045 ms 28516 KB Output is correct
6 Execution timed out 7060 ms 28764 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 39 ms 29020 KB Output is correct
3 Correct 2567 ms 29112 KB Output is correct
4 Correct 3006 ms 28560 KB Output is correct
5 Correct 2045 ms 28516 KB Output is correct
6 Execution timed out 7060 ms 28764 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 39 ms 29020 KB Output is correct
3 Correct 2567 ms 29112 KB Output is correct
4 Correct 3006 ms 28560 KB Output is correct
5 Correct 2045 ms 28516 KB Output is correct
6 Execution timed out 7060 ms 28764 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 294 ms 147632 KB Output is correct
3 Correct 302 ms 147540 KB Output is correct
4 Correct 305 ms 149072 KB Output is correct
5 Correct 233 ms 148924 KB Output is correct
6 Correct 309 ms 147284 KB Output is correct
7 Correct 350 ms 145676 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 39 ms 29020 KB Output is correct
10 Correct 2567 ms 29112 KB Output is correct
11 Correct 3006 ms 28560 KB Output is correct
12 Correct 2045 ms 28516 KB Output is correct
13 Execution timed out 7060 ms 28764 KB Time limit exceeded
14 Halted 0 ms 0 KB -