Submission #1196326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196326		Amr	Dungeons Game (IOI21_dungeons)	C++20	24 / 100	7094 ms	333116 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define sz size()
#define F first
#define S second
typedef long long ll;
const int Log = 25;
const int N = 4e5+3;
ll sp[N][Log],
   spmn[N][Log],
   spsum[N][Log],
   splst[N][Log];

ll m;
vector<int> S , P , W , L;
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
 m = n;
 S = s, P = p, W = w, L = l;
    for(int i = 0; i < n; i++) spmn[i][0] = s[i], spsum[i][0] = p[i], splst[i][0] = p[i],sp[i][0] = l[i];
    spmn[n][0] = -1, splst[n][0] = 0, spsum[n][0] = 0,sp[n][0] = n;

    for(int j = 1; j < Log; j++)
    {
        for(int i = 0; i <= n; i++)
        {
            spmn[i][j] = min(spmn[i][j-1],spmn[sp[i][j-1]][j-1]);
            splst[i][j] = splst[sp[i][j-1]][j-1];
            spsum[i][j] = spsum[i][j-1] + spsum[sp[i][j-1]][j-1];
            sp[i][j] = sp[sp[i][j-1]][j-1];
        }
    }
   //cout << splst[2][2] << endl;
}

long long simulate(int x, int z) {
    ll curp = x, curv = z;
    ll cnt = 5;
    while(curp!=m)
    {
        if(curv<S[curp])
        {
            for(int i = Log-1; i >= 0; i--)
            {
                if(curv+spsum[curp][i]-splst[curp][i]<spmn[curp][i])
                {
                    curv += spsum[curp][i];
                    curp = sp[curp][i];
                }
            }
        }
        else
        {
            curv += S[curp];
            curp = W[curp];
        }
       // cout << curv << " " <<curp << endl;
    }
    return curv;
}

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