제출 #1035048

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1035048		hotboy2703	던전 (IOI21_dungeons)	C++17	100 / 100	2234 ms	2061140 KiB

dungeons

#include "dungeons.h"

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define MASK(i) (1LL<<(i))
#define BIT(mask,i) (((mask) >> (i))&1)
const ll MAXN = 4e5+100;
const ll MAXK = 24;
const ll INF = 1e18;
vector <int> s,p,w,l;
ll n;
struct TABLE{
	struct path{
		ll x,req,sum;
		// < req
	};
	path sp[MAXK][MAXN];
	void build(ll power){
		for (ll i = 0;i < n;i ++){
			if (s[i] > power)sp[0][i] = {l[i],s[i],p[i]};
			else sp[0][i] = {w[i],INF,s[i]};
		}
		sp[0][n] = {n,INF,0};
		for (ll j = 1;j < MAXK;j ++){
			for (ll i = 0;i <= n;i ++){
				sp[j][i].x = sp[j-1][sp[j-1][i].x].x;
				sp[j][i].req = min(sp[j-1][i].req,sp[j-1][sp[j-1][i].x].req - sp[j-1][i].sum);
				sp[j][i].sum = sp[j-1][i].sum + sp[j-1][sp[j-1][i].x].sum;
			}
		}
	}
	void eval(ll &x,ll &z){
		for (ll j = MAXK-1;j >= 0;j --){
			if (sp[j][x].req > z){
				z += sp[j][x].sum;
				x = sp[j][x].x;
			}
		}
		if (x != n){
			z += s[x];
			x = w[x];
		}
	}
};
vector <ll> val;
vector <TABLE> a;

void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
	n=N;
	s=S,p=P,w=W,l=L;
	ll cur = 1;
	val.push_back(cur);
	while (cur < (10'000'000)){
		cur = cur * 10;
		val.push_back(cur);
	}
	a.resize(sz(val));
	for (ll i = 0;i < sz(val);i ++)a[i].build(val[i]);
	return;
}

long long simulate(int X, int Z) {
	ll z=Z;
	ll x=X;
	ll ptr = 0;
	while (x != n){
		while (ptr + 1 < sz(val) && val[ptr+1] <= z)ptr++;
		// cout<<val[ptr]<<endl;
		a[ptr].eval(x,z);
	}
	return z;
}

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