Submission #439896

#	Time	Username	Problem	Language	Result	Execution time	Memory
439896		cheeheng	Dungeons Game (IOI21_dungeons)	C++17	25 / 100	549 ms	93164 KiB

dungeons

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

int S[400005];
int P[400005];
int W[400005];
int L[400005];

int N;

vector<long long> cutoff;
int parent[400005][25][6];
long long cost[400005][25][6];
const long long INF = 1LL << 62;

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
    N = n;
    cutoff.push_back(0);
    cutoff.push_back(INF);
    for(int i = 0; i < N; i ++){
        S[i] = s[i];
        P[i] = p[i];
        W[i] = w[i];
        L[i] = l[i];
        cutoff.push_back(S[i]);
    }

    sort(cutoff.begin(), cutoff.end());
    cutoff.erase(unique(cutoff.begin(), cutoff.end()), cutoff.end());

    assert((int)cutoff.size() <= 7);

    while((int)cutoff.size() < 7){
        cutoff.push_back(INF);
    }

    for(int j = 0; j < 6; j ++){
        for(int i = 0; i < N; i ++){
            parent[i][0][j] = (cutoff[j] >= S[i]) ? W[i] : L[i];
            cost[i][0][j] = (cutoff[j] >= S[i]) ? S[i] : P[i];
        }
        parent[N][0][j] = -1;
    }

    for(int j = 0; j < 6; j ++){
        for(int k = 1; k < 25; k ++){
            for(int i = 0; i <= N; i ++){
                if(parent[i][k-1][j] == -1){
                    parent[i][k][j] = -1;
                }else{
                    parent[i][k][j] = parent[parent[i][k-1][j]][k-1][j];
                    cost[i][k][j] = cost[i][k-1][j] + cost[parent[i][k-1][j]][k-1][j];
                }
            }
        }
    }

	return;
}

long long op = 0;
long long simulate(int x, int z) {
    long long ans = z;
    int cur = x;

    for(int j = 0; j < 6; j ++){
        for(int k = 24; k >= 0; k --){
            if(parent[cur][k][j] != -1){
                long long tempCost = cost[cur][k][j];
                if(ans + tempCost < cutoff[j+1]){
                    ans += tempCost;
                    cur = parent[cur][k][j];
                }
            }
        }

        if(ans < cutoff[j+1]){
            if(parent[cur][0][j] != -1){
                ans += cost[cur][0][j];
                cur = parent[cur][0][j];
            }
        }
        //printf("ans=%lld; cutoff=%lld\n", ans, cutoff[j]);
    }

    assert(cur == N);
	return ans;
}

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