Submission #603842

#	Time	Username	Problem	Language	Result	Execution time	Memory
603842		keta_tsimakuridze	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	2 ms	1364 KiB

dungeons

#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
#include <vector>
vector<int> s, p, w, l;
int n;
const long long inf = 1e9;
const int N =2e5;
long long nxt[N][33][2], add[N][33][2];
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;
    for(int i = 0; i < n; i++) nxt[i][0][0] = l[i], nxt[i][0][1] = w[i], add[i][0][0] = p[i], add[i][0][1] = s[i];
    nxt[n][0][0] = nxt[n][0][1] = n;
    for(int i = 1; i <= 30; i++) {
        for(int j = 0; j <= n; j++) {
            for(int t = 0; t < 2; t++)
            nxt[j][i][t] = nxt[nxt[j][i - 1][t]][j][t],
            add[j][i][t] = add[j][i -  1][t] + add[nxt[j][i - 1][t]][i - 1][t];
        }
    }
}
long long get(int x, int t) {
    long long ans1 = 0;
    for(int i = 30; i >= 0; i--) {
        if(nxt[x][i][t] != n) ans1 += add[x][i][t], x = nxt[x][i][t];
	}
	if(nxt[x][0][t] != n) ans1 = inf;
    return ans1;
}
long long simulate(int x, int z) {
	long long ans1 = get(x, 0) + z, ans2 = z;
    for(int i = 30; i >= 0; i--) {
        if(add[x][i][0] + ans2 < s[0]) {
            ans2 += add[x][i][0];
            x = nxt[x][i][0];
        }
    }
    if(z + add[x][0][0] < s[0]) ans2 = inf;
    x = nxt[x][0][0];
    ans2 += get(x, 1);
    return min(ans1, ans2);
}

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