Submission #898950

#	Time	Username	Problem	Language	Result	Execution time	Memory
898950		Trisanu_Das	던전 (IOI21_dungeons)	C++17	37 / 100	7066 ms	265084 KiB

dungeons

#include "dungeons.h"
 
#include <bits/stdc++.h>
using namespace std; 
 
typedef long long ll;
 
//------------------------------------------------ 

 
int N; 
vector<int> s, p, w, l; 
ll jump[400005][25], jumpSum[400005][25], jumpMX[400005][25];

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
	N=n; 
	::s=s; ::p=p; ::w=w; ::l=l; 
 
	::s.push_back(0); ::p.push_back(0); ::w.push_back(N); ::l.push_back(N); 
 
	for(int i = N; i >= 0; i--){
		if(i == N){
			for(int j = 0; j < 25; j++) jump[i][j] = i, jumpSum[i][j] = 0, jumpMX[i][j] = 0; 
		}
		else{
			jump[i][0] = w[i]; jumpSum[i][0] = s[i]; jumpMX[i][0] = max(s[i], s[w[i]]); 
			for(int j = 1; j < 25; j++){
				jump[i][j] = jump[jump[i][j - 1]][j - 1];
				jumpSum[i][j] = jumpSum[i][j - 1] + jumpSum[jump[i][j - 1]][j - 1];  
				jumpMX[i][j] = max(jumpMX[i][j - 1], jumpMX[jump[i][j - 1]][j - 1]); 
			}
		}
	}
 
}
 
ll simulate(int st, int x){
	int u = st; 
	ll X = x; 
	while(1){
		if(u == N) break;
		if(X >= s[u]){
			for(int i = 24; i >= 0; i--) if(jumpMX[u][i]<=X){
				X += jumpSum[u][i]; 
				u = jump[u][i]; 
			}
			X += jumpSum[u][0]; 
			u = jump[u][0]; 
		}
		else{
			X += p[u]; 
			u = l[u]; 
		}
		
	}
	return X; 
}

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