oj.uz

답안 #896299

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
896299 2024-01-01T07:57:50 Z Ghulam_Junaid 던전 (IOI21_dungeons) C++17
11 / 100
 7000 ms 20832 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll N = 4e5 + 10;

ll n;
vector<ll> s, p, w, l;
vector<ll> win;
ll g[N], start_time[N], tme = 0;
bool subtask2, vis[N];
set<vector<ll>> st;

void dfs(ll v){
    vis[v] = 1;
    start_time[v] = tme;
    st.insert({s[v], tme, v});
    tme++;

    if (!vis[w[v]])
        dfs(w[v]);

    auto ub = st.upper_bound({2 * s[v], -1, -1});
    if (ub == st.end())
        g[v] = -1;
    else
        g[v] = (*ub)[2];

    st.erase({s[v], start_time[v], v});
}

void init(int inp_n, vector<int> S, vector<int> P, vector<int> W, vector<int> L){
    n = inp_n;
    for (ll x : S)
        s.push_back(x);
    for (ll x : P)
        p.push_back(x);
    for (ll x : W)
        w.push_back(x);
    for (ll x : L)
        l.push_back(x);

    memset(g, -1, sizeof g);
    win.resize(n + 1, 0);
    for (ll i = n - 1; i >= 0; i--){
        if (w[i] == n)
            win[i] = s[i];
        else
            win[i] = s[i] + win[w[i]];
    }

    for (ll i = 0; i < n; i ++){
        if (!vis[i]) dfs(i);
    }

    subtask2 = 1;
    for (ll i=0; i<n; i++)
        subtask2 &= (s[i] == p[i]);
}

ll simulate(int x, int z){
    if (subtask2){
        ll cur_node = x;
        ll cur_strength = z;
        while (cur_node != n){
            if (s[cur_node] > cur_strength){
                cur_strength += p[cur_node];
                cur_node = l[cur_node];
            }
            else{
                ll u = g[cur_node];
                if (u == -1){
                    cur_strength += win[cur_node];
                    break;
                }

                cur_strength += win[cur_node] - win[u];
                cur_node = u;
            }
        }

        return cur_strength;
    }

    ll cur_strength = z;
    while (x != n){
        int opp = s[x];
        if (opp > cur_strength){
            cur_strength += p[x];
            x = l[x];
        }
        else{
            cur_strength += s[x];
            x = w[x];
        }
    }
 
    return cur_strength;
}

// int main(){
//     int n, q;
//     cin >> n >> q;

//     vector<int> s(n), p(n), w(n), l(n);
//     for (int i = 0; i < n; i ++) cin >> s[i];
//     for (int i = 0; i < n; i ++) cin >> p[i];
//     for (int i = 0; i < n; i ++) cin >> w[i];
//     for (int i = 0; i < n; i ++) cin >> l[i];

//     init(n, s, p, w, l);
//     while (q--){
//         int x, z;
//         cin >> x >> z;

//         cout << simulate(x, z) << endl;
//     }
// }

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4696 KB Output is correct
2 Correct 1 ms 4952 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 22 ms 9968 KB Output is correct
5 Correct 2 ms 4956 KB Output is correct
6 Correct 23 ms 9808 KB Output is correct

Subtask #2
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 38 ms 11336 KB Output is correct
3 Correct 2098 ms 18120 KB Output is correct
4 Correct 2459 ms 20832 KB Output is correct
5 Correct 1657 ms 17352 KB Output is correct
6 Execution timed out 7042 ms 11100 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 38 ms 11336 KB Output is correct
3 Correct 2098 ms 18120 KB Output is correct
4 Correct 2459 ms 20832 KB Output is correct
5 Correct 1657 ms 17352 KB Output is correct
6 Execution timed out 7042 ms 11100 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4956 KB Output is correct
2 Correct 38 ms 11336 KB Output is correct
3 Correct 2098 ms 18120 KB Output is correct
4 Correct 2459 ms 20832 KB Output is correct
5 Correct 1657 ms 17352 KB Output is correct
6 Execution timed out 7042 ms 11100 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 4956 KB Output isn't correct
2 Halted 0 ms 0 KB -