Submission #626398

#	Time	Username	Problem	Language	Result	Execution time	Memory
626398		juancarlovieri	Dungeons Game (IOI21_dungeons)	C++17	50 / 100	7078 ms	498104 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ll long long

int n;
vector<signed> s, p, w, l;
pair<int, pair<int, int>> win[400005][25];
pair<int, pair<int, int>> los[400005][25];

void init(signed N, std::vector<signed> S, std::vector<signed> P, std::vector<signed> W, std::vector<signed> L) {
  n = N, s = S, p = P, w = W, l = L;
  for (int i = 0; i < n; ++i) {
    win[i][0] = {s[i], {s[i], w[i]}};
    los[i][0] = {s[i] - 1, {p[i], l[i]}};
  }

  for (int j = 1; j < 24; ++j) {
    for (int i = 0; i < n; ++i) {
      if (win[i][j - 1].second.second == n) {
        win[i][j] = win[i][j - 1];
      } else {
        auto lft = win[i][j - 1];
        auto rgt = win[win[i][j - 1].second.second][j - 1];
        int aft = lft.first + lft.second.first;
        win[i][j] = {lft.first + max(0ll, 1ll * rgt.first - aft), {lft.second.first + rgt.second.first, rgt.second.second}};
      }

      if (los[i][j - 1].second.second == n) {
        los[i][j] = los[i][j - 1];
      } else {
        auto lft = los[i][j - 1];
        auto rgt = los[lft.second.second][j - 1];
        int aft = lft.first + lft.second.first;
        los[i][j] = {lft.first - max(0ll, 1ll * aft - rgt.first), {lft.second.first + rgt.second.first, rgt.second.second}};
      }
    }
  }
  return;
}

long long simulate(signed x, signed Z) {
  // int ans = 0;   
  ll z = Z;
  while (x != n) {
    for (int i = 23; i >= 0; --i) {
      if (x == n) break;
      if (win[x][i].first <= z) {
        auto cur = win[x][i];
        x = cur.second.second;
        z += cur.second.first;
      }
    }

    for (int i = 23; i >= 0; --i) {
      if (x == n) break;
      if (los[x][i].first >= z) {
        auto cur = los[x][i];
        x = cur.second.second;
        z += cur.second.first;
      }
    }
  }
  return z;
}

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