제출 #619013

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

dungeons

#include "dungeons.h"
#include <vector>
#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)

int S[1000000];
int P[1000000];
int W[1000000];
int L[1000000];
pair<int,lld> STL[1000000][32];
lld NW[1000000];
int N;
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
	N=n;
	rep(i,0,n){
		S[i]=s[i];
		P[i]=p[i];
		W[i]=w[i];
		L[i]=l[i];
	}
	NW[n]=0;
	for(int i=n-1;i>-1;i--){
		NW[i]=NW[W[i]]+S[i];
	}
	rep(i,0,n){
		STL[i][0]={L[i],P[i]};
	}
	for(int j=1;j<30;j++){
		rep(i,0,n){
			STL[i][j]={STL[STL[i][j-1].first][j-1].first,STL[STL[i][j-1].first][j-1].second+STL[i][j-1].second};
		}
	}
}
#define DEBUG 0
long long simulate(int x, int z) {
	if(DEBUG){
		//cout<<x<<" "<<z<<endl;
		if(x==N)return z;
		if(z<S[x])return simulate(L[x],z+P[x]);
		return simulate(W[x],z+S[x]);
	}else{
		//if(x!=0 || z!=8)cerr<<x<<" "<<z<<endl;
		
		for(int j=29;j>-1;j--){
			if(STL[x][j].second+z<S[x]){
				z+=STL[x][j].second;
				x=STL[x][j].first;
				return simulate(x,z);
			}
		}
		if(z<S[x]){
			return simulate(L[x],z+P[x]);
		}else{
			return z+NW[x];
		}
	}
}

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