oj.uz

Submission #437597

# Submission time Handle Problem Language Result Execution time Memory
437597 2021-06-26T15:37:38 Z Redhood Dungeons Game (IOI21_dungeons) C++17
37 / 100
 7000 ms 155664 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28492 KB Output is correct
2 Correct 21 ms 28408 KB Output is correct
3 Correct 21 ms 28764 KB Output is correct
4 Correct 102 ms 36164 KB Output is correct
5 Correct 23 ms 28728 KB Output is correct
6 Correct 101 ms 36140 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28620 KB Output is correct
2 Correct 534 ms 134024 KB Output is correct
3 Correct 538 ms 155664 KB Output is correct
4 Correct 558 ms 153844 KB Output is correct
5 Correct 862 ms 93012 KB Output is correct
6 Correct 553 ms 137252 KB Output is correct
7 Correct 404 ms 145396 KB Output is correct

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 28620 KB Output is correct
2 Correct 97 ms 36952 KB Output is correct
3 Correct 97 ms 42128 KB Output is correct
4 Correct 85 ms 44320 KB Output is correct
5 Correct 84 ms 42108 KB Output is correct
6 Execution timed out 7017 ms 36892 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 28620 KB Output is correct
2 Correct 97 ms 36952 KB Output is correct
3 Correct 97 ms 42128 KB Output is correct
4 Correct 85 ms 44320 KB Output is correct
5 Correct 84 ms 42108 KB Output is correct
6 Execution timed out 7017 ms 36892 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 28620 KB Output is correct
2 Correct 97 ms 36952 KB Output is correct
3 Correct 97 ms 42128 KB Output is correct
4 Correct 85 ms 44320 KB Output is correct
5 Correct 84 ms 42108 KB Output is correct
6 Execution timed out 7017 ms 36892 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 28620 KB Output is correct
2 Correct 534 ms 134024 KB Output is correct
3 Correct 538 ms 155664 KB Output is correct
4 Correct 558 ms 153844 KB Output is correct
5 Correct 862 ms 93012 KB Output is correct
6 Correct 553 ms 137252 KB Output is correct
7 Correct 404 ms 145396 KB Output is correct
8 Correct 21 ms 28620 KB Output is correct
9 Correct 97 ms 36952 KB Output is correct
10 Correct 97 ms 42128 KB Output is correct
11 Correct 85 ms 44320 KB Output is correct
12 Correct 84 ms 42108 KB Output is correct
13 Execution timed out 7017 ms 36892 KB Time limit exceeded
14 Halted 0 ms 0 KB -