Submission #437597

#	Time	Username	Problem	Language	Result	Execution time	Memory
437597		Redhood	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	7017 ms	155664 KiB

dungeons

#include "dungeons.h"


#include<bits/stdc++.h>
#define fi first
#define se second


#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define len(x) (int)(x).size()
typedef long long ll;
typedef long double ld;
using namespace std;

const int N = (int)4e5 + 10;
vector<int>s,p,w,l;
int n;
vector < int > g[N];
int used[N];
ll ans[N];
int mxS;

pair < int , ll >want[N];
vector<pair<int,ll>> want1[N];
void dfs(int v){
    if(used[v])return;
    used[v] = 1;
    if(v == n)
        return;

    dfs(w[v]);
    ans[v] = ans[w[v]] + s[v];
}

ll pref[N];
int sid[N];
int fen[N];
int id[N];
int h[N];
vector<int> SID[N];
vector<vector<pair<int,int>>>keep;
vector<pair<int,int>>was;



void modify(int x , int val){
    keep.pb({});
    for(; x < N; x += x &- x){
        keep.back().pb({x , fen[x]});
        fen[x] = max(fen[x] , val);
    }
}
int get(int x){
    int mx = 0;
    for(; x > 0 ; x -= x &- x)
        mx = max(mx , fen[x]);
    return mx;
}
void rollback(){
    for(auto u : keep.back())
        fen[u.fi] = u.se;
    keep.pop_back();
}
vector<int>pred;
void dfs1(int v, int H, ll P){
    h[v] = H;
    pref[v] = P + s[v];
    /// in get
    pred.pb(v);

//    cerr << " LOL " <<  v << ' ' << SID[v] << ' ' << sid[v] << endl;
    if(v != n){
        int hh = get(N-1-sid[v]-1);
        int pp = pred[hh];

        want[v] = {pp , pref[v] - pref[pp]};

        int lst = 0;
        want1[v].resize(len(SID[v]));
        for(auto SI : SID[v]){
            if(sid[v] > SI){
                want1[v][lst] = {v , 0};
            }else{

                hh = get(N-1-SI-1);
                pp = pred[hh];


                want1[v][lst] = {pp , pref[v] - pref[pp]};
            }
            lst++;
        }
    }
//    if(v != n){
        modify(N-1-sid[v], h[v]);
//    }



    for(auto u : g[v]){
        dfs1(u , H+1, pref[v]);
    }
//    if(v != n)
        rollback();
    pred.pop_back();
}
bool eq = 0;
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
    s = S;
    p = P;
    w = W;
    l = L;
    n = N;
    eq = 1;
    for(int x = 0 ; x < n; ++x)
        if(p[x] != s[x])
            eq = 0;
    mxS = *max_element(all(s));
    for(int i = 0 ; i < n; ++i){
        g[w[i]].pb(i);
    }
    for(int i = 0 ; i < n; ++i){
        dfs(i);
    }
    s.pb((int)1e7+1);
    vector<int>srt;
    for(int x = 0 ; x <= n; ++x)
        srt.pb(s[x]);
    sort(all(srt));
    srt.erase(unique(all(srt)) , srt.end());

    for(int x = 0 ; x <= n; ++x)
        sid[x] = lower_bound(all(srt), s[x]) - srt.begin();
    for(int x = 0 ; x < n; ++x){
        /// w[x]
        SID[l[x]].pb(sid[x]);
    }
    for(int x = 0;  x < n; ++x)
        sort(all(SID[x]));
    dfs1(n , 0 , 0);
	return;
}

long long simulate(int x, int Z) {
    long long z = Z;
    while(x != n){

        if(z >= mxS){
            z += ans[x];
            x = n;
            continue;
        }

        if(z >= s[x]){
            z += want[x].se;
            x = want[x].fi;
            continue;
        }
//        cerr << " GO by L\n" << x << ' ' << l[x] << ' ' << p[x] <<  ' ' << s[x] << endl;
        int P = sid[x];
        z += p[x], x = l[x];
        /// and now we want to go for it

        if(eq){
            if(x != n){


                int f = lower_bound(all(SID[x]), P) - SID[x].begin();



                z += want1[x][f].se;
                x = want1[x][f].fi;
            }
        }

    }
	return z;
}

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