| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1011107 | 1ne | 던전 (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int k = 20;
vector<vector<long long>>table;
vector<vector<long long>>nx;
vector<vector<long long>>sum;
vector<long long>S,P,W,L;
long long N;
void init(long long n, std::vector<long long> s, std::vector<long long> p, std::vector<long long> w, std::vector<long long> l) {
table.resize(n,vector<long long>(k));
nx.resize(n,vector<long long>(k,-1));
sum.resize(n,vector<long long>(k,0));
N = n;
S = s;
P = p;
W = w;
L = l;
for (long long i = 0;i<n;++i){
table[i][0] = s[i];
nx[i][0] = w[i];
sum[i][0] = s[i];
}
for (long long i = 1;i<k;++i){
for (long long j = 0;j<n;++j){
if (nx[j][i - 1] == -1 || nx[j][i - 1] == n)continue;
//cout<<nx[j][i - 1]<<'\n';
nx[j][i] = nx[nx[j][i - 1]][i - 1];
table[j][i] = max(table[j][i - 1],table[nx[j][i - 1]][i - 1] - sum[j][i - 1]);
sum[j][i] = sum[j][i - 1] + sum[nx[j][i - 1]][i - 1];
}
}
return;
}
long long simulate(long long x, long long z) {
long long Z = z;
while(x != N){
// cout<<x<<"->";
long long c = 0;
while(nx[x][c] != -1 && table[x][c] <= Z){
++c;
}
if (c != 0){
Z+=sum[x][c - 1];
x = nx[x][c - 1];
}
if (x != N){
Z+=P[x];
x = L[x];
}
}
// cout<<'\n';
return Z;
}