oj.uz

Submission #601193

# Submission time Handle Problem Language Result Execution time Memory
601193 2022-07-21T12:57:20 Z Valaki2 Dungeons Game (IOI21_dungeons) C++17
25 / 100
 1317 ms 2097152 KB 
#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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 11 ms 11852 KB Output is correct
4 Runtime error 1317 ms 2097152 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 568 ms 549352 KB Output is correct
2 Runtime error 1114 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1236 KB Output is correct
2 Correct 101 ms 46256 KB Output is correct
3 Correct 122 ms 46208 KB Output is correct
4 Correct 97 ms 45772 KB Output is correct
5 Correct 93 ms 45716 KB Output is correct
6 Correct 113 ms 45956 KB Output is correct
7 Correct 113 ms 46540 KB Output is correct
8 Correct 93 ms 46284 KB Output is correct
9 Correct 101 ms 46224 KB Output is correct
10 Correct 90 ms 46156 KB Output is correct
11 Correct 117 ms 46528 KB Output is correct
12 Correct 209 ms 46452 KB Output is correct
13 Correct 216 ms 46540 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1236 KB Output is correct
2 Correct 101 ms 46256 KB Output is correct
3 Correct 122 ms 46208 KB Output is correct
4 Correct 97 ms 45772 KB Output is correct
5 Correct 93 ms 45716 KB Output is correct
6 Correct 113 ms 45956 KB Output is correct
7 Correct 113 ms 46540 KB Output is correct
8 Correct 93 ms 46284 KB Output is correct
9 Correct 101 ms 46224 KB Output is correct
10 Correct 90 ms 46156 KB Output is correct
11 Correct 117 ms 46528 KB Output is correct
12 Correct 209 ms 46452 KB Output is correct
13 Correct 216 ms 46540 KB Output is correct
14 Correct 5 ms 2772 KB Output is correct
15 Correct 219 ms 101452 KB Output is correct
16 Correct 290 ms 129008 KB Output is correct
17 Correct 299 ms 155804 KB Output is correct
18 Correct 347 ms 155920 KB Output is correct
19 Correct 363 ms 156120 KB Output is correct
20 Correct 244 ms 101052 KB Output is correct
21 Correct 306 ms 128628 KB Output is correct
22 Correct 169 ms 73840 KB Output is correct
23 Correct 383 ms 128696 KB Output is correct
24 Correct 388 ms 101324 KB Output is correct

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1236 KB Output is correct
2 Correct 101 ms 46256 KB Output is correct
3 Correct 122 ms 46208 KB Output is correct
4 Correct 97 ms 45772 KB Output is correct
5 Correct 93 ms 45716 KB Output is correct
6 Correct 113 ms 45956 KB Output is correct
7 Correct 113 ms 46540 KB Output is correct
8 Correct 93 ms 46284 KB Output is correct
9 Correct 101 ms 46224 KB Output is correct
10 Correct 90 ms 46156 KB Output is correct
11 Correct 117 ms 46528 KB Output is correct
12 Correct 209 ms 46452 KB Output is correct
13 Correct 216 ms 46540 KB Output is correct
14 Correct 5 ms 2772 KB Output is correct
15 Correct 219 ms 101452 KB Output is correct
16 Correct 290 ms 129008 KB Output is correct
17 Correct 299 ms 155804 KB Output is correct
18 Correct 347 ms 155920 KB Output is correct
19 Correct 363 ms 156120 KB Output is correct
20 Correct 244 ms 101052 KB Output is correct
21 Correct 306 ms 128628 KB Output is correct
22 Correct 169 ms 73840 KB Output is correct
23 Correct 383 ms 128696 KB Output is correct
24 Correct 388 ms 101324 KB Output is correct
25 Runtime error 1050 ms 2097152 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 568 ms 549352 KB Output is correct
2 Runtime error 1114 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -