제출 #1237336

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1237336		AlperenT_	던전 (IOI21_dungeons)	C++20	63 / 100	7104 ms	301804 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h> 
#pragma GCC optimize("O3,unroll-loops") 
#pragma GCC target("avx2") 
#define pb push_back
#define F first
#define pii pair<int,int> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long 
using namespace std ;
const int maxn = 4e5 + 10  , lg = 29, inf = 1e9+ 10 , S = 15000, mod = 998244353;
int s[maxn] , p[maxn] , w[maxn], l[maxn] , n ;
ll sm[maxn][lg+1] , mn[maxn][lg+1] ; 
int par[maxn][lg+1] ,mx , is[maxn][lg+1] ; 
void init(int N, std::vector<int> s2, std::vector<int> p2, std::vector<int> w2, std::vector<int> l2) {
	n = N ;
	rep(i , 0, n-1){
		s[i] = s2[i];
		mx=max(mx ,s[i]) ;
		p[i] = p2[i] ;
		l[i] =l2[i];
		w[i] = w2[i] ;
	}
	w[n] = l[n] = n ;
	s[n] = p[n] = 0 ;
	rep(i ,0 , lg){
		par[n][i] = n ;
		is[n][i] = 1; 
		mn[n][i] = 0 ;
	}
	rep(i ,0 , n-1){
		if(s[i] < S){
			sm[i][0] = s[i] ;
			par[i][0] = w[i] ;
			is[i][0] = (w[i]==n); 
			mn[i][0] = inf  ;
		}else{
			sm[i][0] = p[i] ;
			par[i][0] = l[i]; 
			is[i][0] = (l[i] == n) ;
			mn[i][0] = s[i] ;
		}
	}
	rep(j , 1  ,lg){
		rep(i , 0 ,n-1){
			par[i][j] = par[par[i][j-1]][j-1] ;
			is[i][j] = is[i][j-1] | is[par[i][j-1]][j-1] ;
			sm[i][j] = sm[i][j-1] + sm[par[i][j-1]][j-1] ;
			mn[i][j] = min(mn[i][j-1] , mn[par[i][j-1]][j-1] - sm[i][j-1]) ;
		}
	}
	return;
}
int x;
ll z ;
inline void nx(){
	if(s[x] <= z){
		z += s[x];
		x = w[x];
	}else{
		z += p[x];
		x = l[x]; 
	}
}

long long simulate(int X, int Z) {
	x = X ;
	z = Z ;
	while(x!=n && z <= S){
		nx();
	}
	if(x==n)return z;
	while(z < mx && x!=n){
		per(i , lg ,1){
			if(mn[x][i-1] <= z || is[x][i-1]){
				continue ;
			}
			z += sm[x][i-1]; 
			x = par[x][i-1]; 
		}
		nx();
	}
	if(x==n)return z ;
	while(x!=n){
		nx(); 
	}
	return z;
}

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