# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1209209 | badge881 | Dungeons Game (IOI21_dungeons) | C++20 | 0 ms | 0 KiB |
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> p, l;
vector<vector<vector<int64_t>>> j2;
vector<vector<vector<pair<int, int64_t>>>> j;
set<int> ssl;
vector<int> sl;
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l)
{
::n = n;
ssl.insert(0);
for (int i = 0; i < n; i++)
ssl.insert(s[i]);
if (ssl.size() <= 6)
{
for (int x : ssl)
sl.push_back(x);
sort(sl.begin(), sl.end());
j.assign(sl.size(), vector<vector<pair<int, int64_t>>>(n + 1, vector<pair<int, int64_t>>(20)));
for (int x = 0; x < sl.size(); x++)
{
j[x][n][0] = {n, 0};
for (int i = 0; i < n; i++)
{
if (sl[x] >= s[i])
j[x][i][0] = {w[i], s[i]};
else
j[x][i][0] = {l[i], p[i]};
}
}
for (int x = 0; x < sl.size(); x++)
{
for (int k = 1; k < 20; k++)
{
for (int i = 0; i <= n; i++)
j[x][i][k] = {j[x][j[x][i][k - 1].first][k - 1].first, j[x][i][k - 1].second + j[x][j[x][i][k - 1].first][k - 1].second};
}
}
return;
}
::p = p;
::l = l;
j2.assign(n + 1, vector<vector<int64_t>>(20, vector<int64_t>(3)));
j2[n][0] = {n, 0, 0};
for (int i = 0; i < n; i++)
j2[i][0] = {w[i], s[i], s[i]};
for (int k = 1; k < 20; k++)
{
for (int i = 0; i <= n; i++)
j2[i][k] = {j2[j2[i][k - 1][0]][k - 1][0], j2[i][k - 1][1] + j2[j2[i][k - 1][0]][k - 1][1], max(j2[i][k - 1][2], j2[j2[i][k - 1][0]][k - 1][2] - j2[i][k - 1][1])};
}
return;
}
int64_t simulate(int x, int iz)
{
int64_t z = iz;
if (ssl.size() > 6)
{
while (x != n)
{
for (int k = 19; k >= 0; k--)
{
if (z >= j2[x][k][2])
{
z += j2[x][k][1];
x = j2[x][k][0];
}
}
if (x != n)
{
z += p[x];
x = l[x];
}
}
return z;
}
int y;
for (int i = 0; i < sl.size(); i++)
{
if (z >= sl[i])
y = i;
}
while (x != n)
{
for (int k = 19; k >= 0; k--)
{
if (y + 1 == sl.size() || z + j[y][x][k].second < sl[y + 1])
{
z += j[y][x][k].second;
x = j[y][x][k].first;
}
}
z += j[y][x][0].second;
x = j[y][x][0].first;
for (int i = 0; i < sl.size(); i++)
{
if (z >= sl[i])
y = i;
}
}
return z;
}