Submission #1108806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108806		abczz	Dungeons Game (IOI21_dungeons)	C++17	63 / 100	1880 ms	2097152 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <array>
#include <cstring>
#include <queue>
#define ll long long
 
using namespace std;
 
vector <ll> V[25];
vector<array<ll, 3>> bl[400001][25];
ll nx[400001];
array <ll, 2> cycsz[400001][25];
queue <ll> Q;
ll n, S[400001], P[400001], A[400001], B[400001], ty[400001], in[400001];
array<ll, 2> dfs(ll u, ll id, ll w, ll x) {
  --in[u];
  if (in[nx[u]]) return cycsz[u][id] = dfs(nx[u], id, w+(ty[u] <= 1 ? P[u] : S[u]), x+1);
  else return cycsz[u][id] = {w+(ty[u] <= 1 ? P[u] : S[u]), x+1};
}
void build_graph(ll id) {
  for (int i=0; i<=n; ++i) in[i] = 0;
  nx[n] = n, in[n] = 1;
	for (int i=0; i<n; ++i) {
		if (ty[i] <= 1) bl[i][id][0] = {B[i], S[i], P[i]}, nx[i] = B[i];
		else bl[i][id][0] = {A[i], (ll)1e18, S[i]}, nx[i] = A[i];
    ++in[nx[i]];
	}
  for (int i=0; i<n; ++i) if (!in[i]) Q.push(i);
  while (!Q.empty()) {
    auto u = Q.front();
    Q.pop();
    --in[nx[u]];
    if (!in[nx[u]]) Q.push(nx[u]);
  }
  for (int i=0; i<n; ++i) {
    if (in[i]) dfs(i, id, 0, 0);
  }
  bl[n][id][0] = {n, (ll)1e18, 0};
  for (int j=1; j<20; ++j) {
    for (int i=0; i<n; ++i) {
      bl[i][id][j][0] = bl[bl[i][id][j-1][0]][id][j-1][0];
      bl[i][id][j][1] = min(bl[i][id][j-1][1], bl[bl[i][id][j-1][0]][id][j-1][1]-bl[i][id][j-1][2]);
      bl[i][id][j][2] = bl[i][id][j-1][2] + bl[bl[i][id][j-1][0]][id][j-1][2];
    }
    bl[n][id][j] = {n, (ll)1e18, 0};
  }
}
 
array<ll, 2> lift(ll id, ll x, ll z) {
  for (int j=19; j>=0; --j) {
    if (bl[x][id][j][1] > z) {
      z += bl[x][id][j][2];
      x = bl[x][id][j][0];
    }
  }
  if (x == n) return {x, z};
  if (z < bl[x][id][19][1]) {
    z += (ll)(max(0LL, bl[x][id][19][1]-z) / cycsz[x][id][0]) * cycsz[x][id][0];
  }
  for (int j=19; j>=0; --j) {
    if (bl[x][id][j][1] > z) {
      z += bl[x][id][j][2];
      x = bl[x][id][j][0];
    }
  }
  return {x, z};
}
void init(int N, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
	n = N;
  for (int i=0; i<=n; ++i) {
    for (int j=0; j<25; ++j) {
      bl[i][j].resize(20);
    }
  }
	for (int i=0; i<n; ++i) {
		S[i] = s[i], P[i] = p[i], A[i] = w[i], B[i] = l[i];
		V[(ll)log2(S[i])].push_back({i});
	}
	for (int i=0; i<25; ++i) {
		for (auto u : V[i]) ty[u] = 1;
    build_graph(i);
		for (auto u : V[i]) ty[u] = 2;
	}
}
 
long long simulate(int x, int z) {
  ll a = x, b = z;
  while (a != n) {
    auto y = (ll)log2(b);
    y = min(y, 24LL);
    auto [u, v] = lift(y, a, b);
    a = u, b = v;
    if (a == n) break;
    b += S[a], a = A[a];
  }
	return b;
}

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