제출 #896736

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
896736		Ghulam_Junaid	던전 (IOI21_dungeons)	C++17	11 / 100	7058 ms	107916 KiB

dungeons

#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, answers;
ll g[N], start_time[N], tme = 0, rev_time[N];
bool subtask2, vis[N];
set<pair<ll, ll>> st;
vector<ll> graph[N];

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

    for (ll u : graph[v])
        if (!vis[u]) dfs(u);

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

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

}

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);
    s.push_back(1e9);
    p.push_back(1e9);
    w.push_back(n);
    l.push_back(n);

    win.resize(n + 1, 0);
    for (ll i = n - 1; i >= 0; i--)
        win[i] = s[i] + win[w[i]];

    for (ll i=0; i<n; i++)
        graph[w[i]].push_back(i);
    memset(g, -1, sizeof g);

    dfs(n);

    // for (int i = 0; i < n; i++){
    //     int cur = w[i];
    //     while (cur != n){
    //         if (s[cur] > 2 * s[i]){
    //             if (cur != g[i]){
    //                 cout << "opps " << i << " " << cur << " found " << g[i] << endl;
    //             }
    //             break;
    //         }
    //         cur = w[cur];
    //     }
    // }

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

ll simulate(int x, int z){
    // cout << x << " " << z << endl;
    if (subtask2){
        ll cur_node = x;
        ll cur_strength = z;
        while (cur_node < n){
            // cout << cur_node << endl;
            if (s[cur_node] > cur_strength){
                cur_strength += p[cur_node];
                cur_node = l[cur_node];
            }
            else{ 
                ll u = g[cur_node];
                // cout << cur_node << " ,, " << u << endl;
                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){
        ll 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;
}

• Subtask 1: 11 / 11
• Subtask 2: 0 / 26
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11