제출 #612485

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
612485		AmirElarbi	던전 (IOI21_dungeons)	C++17	11 / 100	7065 ms	46436 KiB

dungeons

#include <bits/stdc++.h>
#define vi vector<int>
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 2e9+5
#define eps 1e-7
#define eps1 1e-25
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
#define V 450
using namespace std;
const int MOD = 1e9;
const int nax = 5e4+5;
const int lg = 25;
#include "dungeons.h"
int nxt[nax][lg], sm[nax][lg], mx[nax][lg], n;
vi s,p,w,l;
void init(int N, vi S, vi P, vi W, vi L) {
    n = N; 
    s = S, p = P, w = W, l = L;
    s.pb(0);
    for (int i = 0; i < lg; ++i)
    {
        nxt[n][i] = n, sm[n][i] = 0, mx[n][i] = 0;
    }
    for (int i = n-1; i >= 0; --i)
    {
        nxt[i][0] = w[i], sm[i][0] = s[i], mx[i][0] = max(s[w[i]],s[i]);
        //cout << w[i] << endl;
        for (int j = 1; j < lg; ++j)
        {
            nxt[i][j] = nxt[nxt[i][j-1]][j-1];
            sm[i][j] = sm[i][j-1] + sm[nxt[i][j-1]][j-1];
            mx[i][j] = max(mx[i][j-1], mx[nxt[i][j-1]][j-1]);
        }
    }
}

long long simulate(int x, int z) {
    while(x != n){
        if(z >= s[x]){
            for (int i = 0; i < lg; ++i)
            {
                if(mx[x][i] <= z){
                    z += sm[x][i];
                    x = nxt[x][i];
                }
            }

            z += sm[x][0];
            x = nxt[x][0];
        } else {
            z += p[x], x = l[x];
        }
    }
    return z;
}

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