제출 #1195853

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195853		Nonoze	던전 (IOI21_dungeons)	C++20	25 / 100	1128 ms	2162688 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fi first
#define se second

const int LOG=30;

vector<int> s, p, w, l, dist, values;
vector<vector<vector<pair<int, int>>>> up;
int n, m;


void init(signed _n, vector<signed> _s, vector<signed> _p, vector<signed> _w, vector<signed> _l) {
	set<int> st; for (auto &u: _s) st.insert(u);
	for (auto &u: st) values.pb(u);
	n=_n, m=(int)values.size();
	for (auto &u: _s) s.pb(u);
	for (auto &u: _p) p.pb(u);
	for (auto &u: _w) w.pb(u);
	for (auto &u: _l) l.pb(u);
	dist.resize(n+1); dist[n]=0;
	for (int i=n-1; i>=0; i--) dist[i]=dist[w[i]]+s[i];
	up.resize(m, vector<vector<pair<int, int>>>(n+1, vector<pair<int, int>>(LOG, {n, 0})));
	for (int x=0; x<m; x++) {
		for (int i=0; i<n; i++) {
			up[x][i][0]={l[i], p[i]};
			if (s[i]<values[x]) up[x][i][0]={w[i], s[i]};
		}
		for (int bit=1; bit<LOG; bit++) {
			for (int i=0; i<n; i++) {
				up[x][i][bit]=up[x][up[x][i][bit-1].fi][bit-1];
				up[x][i][bit].se+=up[x][i][bit-1].se;
			}
		}
	}
	return;
}


int simulate(signed x, signed z) {
	int ans=z;
	for (int cur=0; cur<m; cur++) {
		for (int bit=LOG-1; bit>=0; bit--) {
			if (up[cur][x][bit].fi!=n && up[cur][x][bit].se+ans<values[cur]) ans+=up[cur][x][bit].se, x=up[cur][x][bit].fi;
		}
		if (ans<values[cur] && x!=n) ans+=up[cur][x][0].se, x=up[cur][x][0].fi;
	}
	return ans+dist[x];
}

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