Submission #601193

#	Time	Username	Problem	Language	Result	Execution time	Memory
601193		Valaki2	Dungeons Game (IOI21_dungeons)	C++17	25 / 100	1317 ms	2097152 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

#define n N
#define s S
#define p P
#define w W
#define l L

#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

const int logn = 31;
const int inf = 4e16 + 42;

int n;
vector<int> win_str, lose_str, win_pos, lose_pos;
int k;
vector<vector<vector<int> > > lift_str;
vector<vector<vector<int> > > lift_pos;
map<int, int> conv;
vector<int> val;
vector<int> cost;

void solve() {
    for(int i = 0; i < n; i++) {
        conv[win_str[i]] = -1;
    }
    //conv[inf] = -1;
    k = (int) conv.size();
    val.assign(k, 0);
    int val_idx = -1;
    vector<pii > v;
    for(const pii &p : conv) {
        val_idx++;
        v.pb(mp(p.fi, val_idx));
        val[val_idx] = p.fi;
    }
    conv.clear();
    for(const pii &p : v) {
        conv[p.fi] = p.se;
    }
    lift_str = lift_pos = vector<vector<vector<int> > > (k, vector<vector<int> > (1 + n, vector<int> (logn, 0)));
    int minimum_value = 0; // these are already won
    for(int cur_idx = 0; cur_idx < k; cur_idx++) {
        vector<vector<int> > &cur_lift_str = lift_str[cur_idx];
        vector<vector<int> > &cur_lift_pos = lift_pos[cur_idx];
        for(int i = 0; i <= n; i++) {
            if(win_str[i] <= minimum_value) {
                cur_lift_str[i][0] = win_str[i];
                cur_lift_pos[i][0] = win_pos[i];
            } else {
                cur_lift_str[i][0] = lose_str[i];
                cur_lift_pos[i][0] = lose_pos[i];
            }
        }
        for(int j = 1; j < logn; j++) {
            for(int i = 0; i <= n; i++) {
                cur_lift_str[i][j] = cur_lift_str[i][j - 1] + cur_lift_str[cur_lift_pos[i][j - 1]][j - 1];
                cur_lift_pos[i][j] = cur_lift_pos[cur_lift_pos[i][j - 1]][j - 1];
            }
        }
        minimum_value = val[cur_idx];
    }
    cost.assign(1 + n, 0);
    for(int i = n - 1; i >= 0; i--) {
        cost[i] = win_str[i] + cost[win_pos[i]];
    }
}

int query(int pos, int strength) {
    /*if(strength >= k) {
        return strength + cost[pos];
    }
    for(int j = logn - 1; j >= 0; j--) {
        if(strength + lift_str[pos][j] < k) {
            strength += lift_str[pos][j];
            pos = lift_pos[pos][j];
        }
    }
    strength += lift_str[pos][0];
    pos = lift_pos[pos][0];
    return strength + cost[pos];*/
    for(int cur_idx = 0; cur_idx < k; cur_idx++) {
        if(strength >= val[cur_idx]) {
            continue;
        }
        //cout << cur_idx << " - " << val[cur_idx] << ": " << pos << " " << strength << endl;
        for(int j = logn - 1; j >= 0; j--) {
            if(strength + lift_str[cur_idx][pos][j] < val[cur_idx]) {
                strength += lift_str[cur_idx][pos][j];
                pos = lift_pos[cur_idx][pos][j];
            }
        }
        //cout << cur_idx << " - " << val[cur_idx] << ": " << pos << " " << strength << endl;
        strength += lift_str[cur_idx][pos][0];
        pos = lift_pos[cur_idx][pos][0];
    }
    //cout << "last one: " << pos << " " << strength << endl;
    return strength + cost[pos];
}

#undef n
#undef s
#undef p
#undef w
#undef l
void init(signed n, vector<signed> s, vector<signed> p, vector<signed> w, vector<signed> l) {
	N = n;
	win_str = lose_str = win_pos = lose_pos = (vector<int> (n + 1, 0));
	for(int i = 0; i < n; i++) {
        win_str[i] = s[i];
        lose_str[i] = p[i];
        win_pos[i] = w[i];
        lose_pos[i] = l[i];
	}
	win_str[n] = 0;
	lose_str[n] = 0;
	win_pos[n] = n;
	lose_pos[n] = n;
	solve();
}

int simulate(signed x, signed z) {
	return query(x, z);
}

/*
3 1
2 6 9
3 1 2
2 2 3
1 0 1
0 1
*/

/*
3 2
2 6 9
3 1 2
2 2 3
1 0 1
0 1
2 3
*/

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