Submission #1108648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108648		abczz	Dungeons Game (IOI21_dungeons)	C++17	11 / 100	994 ms	735844 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <array>
#include <cstring>
#include <queue>
#define ll int

using namespace std;

vector <ll> V[25];
vector<array<ll, 3>> bl[50001][25];
ll nx[400001], cycsz[400001][25];
queue <ll> Q;
ll n, S[400001], P[400001], A[400001], B[400001], ty[400001], in[400001];
ll dfs(ll u, ll id, ll w) {
  --in[u];
  if (in[nx[u]]) return cycsz[u][id] = dfs(nx[u], id, w+(ty[u] <= 1 ? P[u] : S[u]));
  else return cycsz[u][id] = w+(ty[u] <= 1 ? P[u] : S[u]);
}
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)1e9, 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(u);
  }
  for (int i=0; i<n; ++i) {
    if (in[i]) dfs(i, id, 0);
  }
  bl[n][id][0] = {n, (ll)1e9, 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)1e9, 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 < S[x]) z += (ll)(max(0, bl[x][id][19][1]-z) / cycsz[x][id]) * cycsz[x][id];
  else return {x, 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];
    }
  }
  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) {
  while (x != n) {
    auto y = (ll)log2(z);
    auto [u, v] = lift(y, x, z);
    x = u, z = v;
    if (x == n) break;
    z += S[x], x = A[x];
  }
	return z;
}

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