| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 438268 | PiejanVDC | 던전 (IOI21_dungeons) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
int nnn;
vector<int>sss,ppp,www,lll;
vector<long long>winning_path;
//vector<int>adj[400001];
void gen(void);
void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll) {
nnn=nn;
sss=ss,ppp=pp,www=ww,lll=ll;
/*for(int i = 0 ; i < nnn ; i++) {
adj[www[i]].push_back(i);
}*/
gen();
}
void gen(void) {
vector<bool>vis(nnn+1,false);
winning_path.resize(nnn+1);
winning_path[nnn]=0;
for(int i = 0 ; i < nnn ; i++) {
next=i;
long long cnt=0;
while(next!=nnn) {
cnt++;
next=www[next];
}
winning_path[i]=cnt;
}
}
long long simulate(int x, int zz) {
vector<pair<bool,long long>>v(nnn+1,{false,0});
vector<long long> seq;
long long curr=0, len=0;
long long z=zz;
while(true) {
if(v[x].first) {
long long ans = (sss[x]-z)/(curr-v[x].second);
z+=ans*(curr-v[x].second);
int left=0, right=seq.size()-1, use=x;
while(left <= right) {
int mid = (left+right)/2;
if(z+(v[seq[mid]].second-v[x].second) >= sss[x]) {
use=mid;
right=mid-1;
} else {
left=mid+1;
}
}
if(use>0&&use<seq.size()){
z+=v[seq[use]].second - v[x].second;
x=seq[use];
}
}
if(x==nnn) return z;
if(z >= sss[x]) {
long long mul = sss[x]*winning_path[x];
return z+mul;
}
v[x].first=true,v[x].second=curr;
z+=ppp[x], curr+=ppp[x];
seq.push_back(x);
x=lll[x];
len++;
}
}