Submission #896284

#	Time	Username	Problem	Language	Result	Execution time	Memory
896284		Ghulam_Junaid	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	141 ms	4432 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;
ll g[N];
bool subtask2, vis[N];
set<pair<int, int>> st;

void dfs(int v){
    vis[v] = 1;
    st.insert({s[v], v});

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

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

    st.erase({s[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 (int i = 0; i < n; i ++){
        if (!vis[i]) dfs(i);
    }

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

ll simulate(int x, int z){
    ll cur_strength = z;
    while (x != n){

        cout << x << " " << cur_strength << endl;
        ll opp = s[x];
        if (opp > cur_strength){
            cur_strength += p[x];
            x = l[x];
        }
        else{
            int u = g[x];
            if (u == -1){
                cur_strength += win[x];
                break;
            }

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

    return cur_strength;
}

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