| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 809051 | Benmath | 던전 (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
long long int type[7][400001][31];
int loc[7][400001][31];
int k=1;
int tip[10000001];
vector<long long int>tipovi;
void init(int n1, std::vector<int> s1, std::vector<int> p1, std::vector<int> w1, std::vector<int> l1) {
n=n1;
for(int i=0;i<n;i++){
s[i]=s1[i];
p[i]=p1[i];
w[i]=w1[i];
l[i]=l1[i];
}
sort(s1.begin(),s1.end());
tipovi.push_back(s1[0]);
tip[s1[0]]=0;
for(int i=1;i<n;i++){
if(s1[i]>s1[i-1]){
tipovi.push_back(s1[i]);
tip[s1[i]]=k;
k++;
}
}
for(int t=0;t<=k;t++){
for(int j=0;j<=30;j++){
for(int i=n;i>=0;i--){
if(i==n){
type[t][i][j]=0;
loc[t][i][j]=n;
}else{
if(j==0){
int ro=tip[s1[i]];
if(t>ro){
type[t][i][j]=s[i];
loc[t][i][j]=w[i];
}else{
type[t][i][j]=p[i];
loc[t][i][j]=l[i];
}
}else{
loc[t][i][j]=loc[t][loc[t][i][j-1]][j-1];
type[t][i][j]=type[t][i][j-1]+type[t][loc[t][i][j-1]][j-1];
}
}
}
}
}
}
long long simulate(int x, int z) {
int neki;
int t1=0;
long long int total=z;
int lok=x;
while(t1==0){
if(total<tipovi[0]){
neki=0;
}
int ro=tipovi.size();
if(total>=tipovi[ro-1]){
neki=ro;
return (total+type[neki][lok][30]);
}
for(int i=0;i<ro;i++){
if(i!=(ro-1)){
if(total>=tipovi[i] and total<tipovi[i+1]){
neki=i+1;
}
}
}
for(int j=30;j>=0;j--){
if((total+type[neki][lok][j])<tipovi[neki]){
total=total+type[neki][lok][j];
lok=loc[neki][lok][j];
}
}
total=total+type[neki][lok][0];
lok=loc[neki][lok][0];
if(lok==n){
return total;
}
}
}