oj.uz

답안 #928103

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
928103 2024-02-15T20:46:44 Z bobbilyking 던전 (IOI21_dungeons) C++17
13 / 100
 1699 ms 68664 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long ;
#define A(a) (a).begin(), (a).end()
using pl = pair<ll, ll>;
using vl = vector<ll>;
#define F(i, l, r) for (ll i = (l); i < (r); ++i)
#define FD(i, l, r) for (ll i = (l); i > (r); --i)
#define K first
#define V second

const ll NN = 5e4+10;
// const ll NN = 4e5+10;
// const ll SN = 0;
const ll SN = 3200;

ll n;

ll s[NN], p[NN], w[NN], l[NN];

// We need this, because this lets us win fast. Otherwise ,would  take O(n) even when strength >> 1e7
pl ans[NN]; // {minimum strength needed to clear to root, bonus delta }


using T = pl;
const ll L = 26;
pl lift[NN][L];
ll par[NN][L];

constexpr ll INF = 1e18;

T f(T a, T b) {
    T res;
    res.K = min(a.K, b.K - a.V);
    res.V = min(2*INF, a.V + b.V);
    
    return res;
}

void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
    n = _n;
    copy(A(_s), s);
    copy(A(_p), p);
    copy(A(_w), w);
    copy(A(_l), l);

    // precomp ans
    FD(i, n-1, -1) {
        ans[i].K = max(s[i], ans[w[i]].K - s[i]);   
        ans[i].V = ans[w[i]].V + s[i];
    }

    F(i, 0, n) {
        if (s[i] > SN) {
            par[i][0] = l[i];
            lift[i][0] = {s[i], p[i]};
        } else {
            // when strength > SN, we always win here, so fix these to be winning edge. 
            par[i][0] = w[i];
            lift[i][1] = {s[i], s[i]};
        } 
    }
    F(i, 0, L) lift[n][i] = {-INF, 0};

    F(l, 1, L) F(i, 0, n) {
        par[i][l] = par[par[i][l-1]][l-1];
        lift[i][l] = f(lift[i][l-1], lift[par[i][l-1]][l-1]);
    }

    // F(i, 0, n) {
    //     F(l, 0, L) cout << lift[i][l].K << " " << lift[i][l].V << " | ";
    //     cout << endl;
    // }

}

long long simulate(int _x, int _z) {
    ll x = _x, z = _z;

    ll moves = 0;

    auto iterate1 = [&]{
        if (z >= s[x]) {
            // cout << "ADDED UP " << s[x] << endl;
            z += s[x], x = w[x];
        }
        else {
            // cout << "ADDED DOWN " << p[x] << endl;
            z += p[x], x = l[x];
        }

        ++moves;
    };

    while (x != n and z <= SN) {
        iterate1();
    }

    if (x == n) return z;

    // TODO: implement some kind of bsearch dictating how far to go while taking
    // only "losing" edges

    // cout << "Currently: " << x << " " << z << endl;

    while (1) {    
        if (ans[x].K <= z) return ans[x].V + z;
        // cout << "Started with " << x << " " << z << endl;
        // figure out where to jump, then update x and z. We are now at a winning node.
        // if (0)
        FD(l, L-1, -1) {
            const auto &[thresh, sm] = lift[x][l];

            // if (l == 1) {
            //     cout << "Why not jump here? " << endl;
            //     cout << thresh << " " << sm << " | " << z << endl;

            //     auto [a1, b1] = lift[0][0];
            //     auto [a2, b2] = lift[1][0];
                
            //     cout << a1 << " " << b1 << " " << a2 << " " << b2 << endl;
            // }

            // cout << z << " " << thresh << " " << sm << endl;
            if (z < thresh ) {
                x = par[x][l];
                z += sm;

                // cout << "Jumped " << l << endl;
                moves += 1<<l;
            }
        }

        // cout << "WTF U ON " << moves << endl;

        if (x == n) return z;
        // iterate1();
        // cout << "WTF " << x << " " << z << " " << s[x] << endl;
        assert(s[x] > SN);
        assert(z >= s[x]); 
        iterate1(); 
    }
}

Subtask #1
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Runtime error 53 ms 68664 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Runtime error 115 ms 28220 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 46 ms 35632 KB Output is correct
3 Correct 46 ms 35672 KB Output is correct
4 Correct 50 ms 35648 KB Output is correct
5 Correct 40 ms 35676 KB Output is correct
6 Correct 61 ms 35676 KB Output is correct
7 Correct 231 ms 35676 KB Output is correct
8 Correct 55 ms 35672 KB Output is correct
9 Correct 40 ms 35672 KB Output is correct
10 Correct 102 ms 35676 KB Output is correct
11 Correct 1557 ms 35420 KB Output is correct
12 Correct 1699 ms 35676 KB Output is correct
13 Correct 407 ms 35412 KB Output is correct

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 46 ms 35632 KB Output is correct
3 Correct 46 ms 35672 KB Output is correct
4 Correct 50 ms 35648 KB Output is correct
5 Correct 40 ms 35676 KB Output is correct
6 Correct 61 ms 35676 KB Output is correct
7 Correct 231 ms 35676 KB Output is correct
8 Correct 55 ms 35672 KB Output is correct
9 Correct 40 ms 35672 KB Output is correct
10 Correct 102 ms 35676 KB Output is correct
11 Correct 1557 ms 35420 KB Output is correct
12 Correct 1699 ms 35676 KB Output is correct
13 Correct 407 ms 35412 KB Output is correct
14 Runtime error 7 ms 13660 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 46 ms 35632 KB Output is correct
3 Correct 46 ms 35672 KB Output is correct
4 Correct 50 ms 35648 KB Output is correct
5 Correct 40 ms 35676 KB Output is correct
6 Correct 61 ms 35676 KB Output is correct
7 Correct 231 ms 35676 KB Output is correct
8 Correct 55 ms 35672 KB Output is correct
9 Correct 40 ms 35672 KB Output is correct
10 Correct 102 ms 35676 KB Output is correct
11 Correct 1557 ms 35420 KB Output is correct
12 Correct 1699 ms 35676 KB Output is correct
13 Correct 407 ms 35412 KB Output is correct
14 Runtime error 7 ms 13660 KB Execution killed with signal 6
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Runtime error 115 ms 28220 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -