제출 #1037002

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1037002		aaaaaarroz	던전 (IOI21_dungeons)	C++17	100 / 100	2105 ms	2061136 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