제출 #1057649

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1057649		sonamoo	던전 (IOI21_dungeons)	C++17	0 / 100	81 ms	27804 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#define SIZE 400005
#define ll long long

using namespace std;

int n;
ll s[SIZE] , p[SIZE][26];
int w[SIZE] , l[SIZE][26];
ll S;
ll dp[SIZE];

ll dfs(int here) {
    if (here==n) return dp[here]=0;
    if (dp[here] != -1) return dp[here];
    return dp[here] = dfs(w[here])+S;
}

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][0] = _p[i], w[i] = _w[i] , l[i][0] = _l[i];
    S = s[0];
    for (int j = 1; j < 26; j++) {
        for (int i = 0; i < n; i++) {
            p[i][j] = p[i][j-1]+p[l[i][j-1]][j-1];
            l[i][j] = l[l[i][j-1]][j-1];
        }
    }
    memset(dp , -1 , sizeof(dp));
    for (int i = 0; i < n; i++) {
        if (dp[i]==-1) dfs(i);
    }

    return;
}

bool f(int x , int cnt , int z) {
    ll HP = z*1LL;
    for (int j = 25; j >= 0; j--) {
        if (cnt&(1<<j)) {
            HP += p[x][j];
            x = l[x][j];
        }
    }
    if (HP >= S) return true;
    return false;
}

long long simulate(int x, int z) {
    ll HP = z*1LL;
    int lo = 0 , hi = 2e7;
    while(lo < hi) {
        int mid = (lo+hi)/2;
        if (f(x , mid , z)) hi = mid;
        else lo = mid+1;
    }
    for (int j = 25; j >= 0; j--) {
        if (lo&(1<<j)) {
            HP += p[x][j];
            x = l[x][j];
        }
    }
    assert(HP >= S);
    HP += dp[x];

    return HP;
}

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