Submission #439870

#	Time	Username	Problem	Language	Result	Execution time	Memory
439870		cheeheng	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	7041 ms	27960 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;

long long score[400005];
long long winScore[400005];
bool visited[400005];
bool inStack[400005];
int cycleIndx[400005];
int cycleIndx2[400005];
vector<int> cycleList[400005];
vector<long long> prefixSum[400005];

vector<int> stack1;
int cnt1 = 0;
void dfs(int u){
    //printf("dfs(%d)\n", u);
    if(visited[u]){return;}
    visited[u] = true;
    stack1.push_back(u);
    inStack[u] = true;

    /*printf("Stack1: ");
    for(int i: stack1){
        printf("%d ", i);
    }
    printf("\n");*/

    int v = L[u];

    if(visited[v] && inStack[v]){
        long long score2 = 0;
        int indx = (int)stack1.size()-1;
        while(indx >= 0){
            inStack[stack1[indx]] = false;
            //printf("%d\n", stack1[indx]);
            if(stack1[indx] == v){break;}
            indx --;
        }
        assert(indx >= 0);

        for(int i = max(indx, 0); i < (int)stack1.size(); i ++){
            score2 += P[stack1[i]];
        }

        for(int i = max(indx, 0); i < (int)stack1.size(); i ++){
            score[stack1[i]] = score2;
            cycleIndx[stack1[i]] = cnt1;
            cycleIndx2[stack1[i]] = i-(indx+1);
            cycleList[cnt1].push_back(stack1[i]);
            //printf("cnt1=%d stack1[i]=%d\n", cnt1, stack1[i]);
        }

        cnt1 ++;

        while((int)stack1.size() > indx){
            stack1.pop_back();
        }
    }else{
        dfs(v);
    }
}

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

    memset(visited, false, sizeof(visited));
    memset(score, -1, sizeof(score));
    memset(cycleIndx, -1, sizeof(cycleIndx));

    for(int i = 0; i < N; i ++){
        if(!visited[i]){
            for(int j: stack1){
                inStack[j] = false;
            }
            stack1 = vector<int>();
            dfs(i);
        }
    }

    winScore[N] = 0;
    for(int i = N-1; i >= 0; i --){
        winScore[i] += winScore[W[i]] + S[i];
    }

    for(int i = 0; i < cnt1; i ++){
        //printf("i=%d\n", i);
        prefixSum[i].push_back(0);
        //printf("i=%d\n", i);
        for(int j: cycleList[i]){
            //printf("j=%d\n", j);
            prefixSum[i].push_back(prefixSum[i].back() + P[j]);
            //printf("%d %lld %d\n", i, prefixSum[i].back(), j);
        }
        assert(cycleList[i].size());
        assert(prefixSum[i].back() == score[cycleList[i][0]]);
    }

    //printf("here\n");
	return;
}

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

    if(score[cur] > 0 && ans + score[cur] < S[cur]){
        long long req = S[cur] - ans;
        if(req > 0){
            long long cnt = req/score[cur];
            ans += cnt*score[cur];
        }
    }

    while(cur != N){
        //op ++;
        //printf("cur=%d ans=%lld\n", cur, ans);
        if(ans >= S[cur]){
            //ans += S[cur];
            //cur = W[cur];
            ans += winScore[cur];
            break;
        }else{
            //int i = cycleIndx[cur];
            //int indx = cycleIndx2[cur];
            //long long req = (S[cur] - ans + prefixSum[i][indx+1]) % score[cur];

            ans += P[cur];
            cur = L[cur];
        }
    }
    //assert(op <= 2500000000);

	return ans;
}

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