Submission #1318209

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318209		SmuggingSpun	Dungeons Game (IOI21_dungeons)	C++20	100 / 100	3568 ms	1659424 KiB

dungeons

#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>void minimize(T& a, T b){
  if(a > b){
    a = b;
  }
}
const int lim = 4e5 + 5;
int n, subtask_id = -1;
vector<int>s, p, w, l;
namespace sub1{
  int solve(int x, int z){
    while(x < n){
      if(z >= s[x]){
        z += s[x];
        x = w[x];
      }
      else{
        z += p[x];
        x = l[x];
      }
    }
    return z;
  }
}
struct Data{
  int to;
  ll need, sum;
  Data(){}
  Data(int _to, ll _need, ll _sum) : to(_to), need(_need), sum(_sum) {}
};
namespace sub2{
  bool check_subtask(){
    for(int i = 0; i < n; i++){
      if(s[i] != p[i]){
        return false;
      }
    }
    return true;
  }
  vector<Data>up[19];
  void init(){
    for(int i = 0; i < 19; i++){
      up[i].resize(n + 1);
      up[i][n] = Data(n, 0, 0);
    }
    for(int i = 0; i < n; i++){
      up[0][i] = Data(w[i], s[i], s[i]);
    }
    for(int i = 1; i < 19; i++){
      for(int j = 0; j < n; j++){
        up[i][j].to = up[i - 1][up[i - 1][j].to].to;
        up[i][j].need = max(up[i - 1][j].need, up[i - 1][up[i - 1][j].to].need - up[i - 1][j].sum);
        up[i][j].sum = up[i - 1][j].sum + up[i - 1][up[i - 1][j].to].sum;
      }
    }
  }
  ll solve(int x, ll z){
    while(x < n){
      for(int bit = 18; bit > -1; bit--){
        if(up[bit][x].need <= z){
          z += up[bit][x].sum;
          x = up[bit][x].to;
        }
      }
      if(x == n){
        break;
      }
      z += p[x];
      x = l[x];
    } 
    return z;
  }
}
const ll INF = 1e18;
namespace sub34{
  bool check_subtask(){
    if(n > 50000){
      return false;
    }
    unordered_map<int, bool>cnt;
    for(int& x : s){
      cnt[x] = true;
      if(cnt.size() > 5){
        return false;
      }
    }
    return true;
  }
  vector<ll>val_s;
  vector<pair<int, ll>>up[6][24];
  int cnt_s;
  void init(){
    for(int i = 0; i < n; i++){
      if(find(val_s.begin(), val_s.end(), s[i]) == val_s.end()){
        val_s.push_back(s[i]);
      }
    }
    sort(val_s.begin(), val_s.end());
    val_s.push_back(INF);
    cnt_s = val_s.size();
    for(int i = 0; i < cnt_s; i++){
      for(int j = 0; j < 24; j++){
        up[i][j].resize(n + 1);
        up[i][j][n] = make_pair(n, 0);
      }
      for(int j = 0; j < n; j++){
        bool lose = s[j] >= val_s[i];
        up[i][0][j] = make_pair(lose ? l[j] : w[j], lose ? p[j] : s[j]);
      }
      for(int j = 1; j < 24; j++){
        for(int k = 0; k < n; k++){
          up[i][j][k].first = up[i][j - 1][up[i][j - 1][k].first].first;
          up[i][j][k].second = up[i][j - 1][k].second + up[i][j - 1][up[i][j - 1][k].first].second;
        }
      }
    }
  }
  ll solve(int x, ll z){ 
    for(int i = 0; i < cnt_s; i++){
      for(int bit = 23; bit > -1; bit--){
        ll nz = z + up[i][bit][x].second;
        if(nz < val_s[i]){
          z = nz;
          x = up[i][bit][x].first;
        }
      }
      if(x == n){
        break;
      }
      if(z < s[x]){
        z += p[x];
        x = l[x];
      }
      else{
        z += s[x];
        x = w[x];
      }
    }
    return z;
  }
}
namespace sub5{
  vector<Data>up[25][25];
  void init(){
    for(int i = 0; i < 25; i++){
      for(int j = 0; j < 25; j++){
        up[i][j].resize(n + 1);
        up[i][j][n] = Data(n, INF, 0);
      }
      for(int k = 0; k < n; k++){
        if(s[k] > (1 << i)){
          up[i][0][k] = Data(l[k], s[k] - 1, p[k]);
        }
        else{
          up[i][0][k] = Data(w[k], INF, s[k]);
        }
      }
      for(int j = 1; j < 25; j++){
        for(int k = 0; k < n; k++){
          up[i][j][k].to = up[i][j - 1][up[i][j - 1][k].to].to;
          up[i][j][k].need = min(up[i][j - 1][k].need, up[i][j - 1][up[i][j - 1][k].to].need - up[i][j - 1][k].sum);
          up[i][j][k].sum = up[i][j - 1][k].sum + up[i][j - 1][up[i][j - 1][k].to].sum;
        }
      }
    }
  }
  ll solve(int x, ll z){
    for(int i = 0; i < 25; i++){
      if(i == 24 || (1 << (i + 1)) > z){
        for(int j = 24; j > -1; j--){
          if(z <= up[i][j][x].need){
            z += up[i][j][x].sum;
            x = up[i][j][x].to;
          }
        }
        if(x == n){
          break;
        }
        if(z < s[x]){
          z += p[x];
          x = l[x];
        }
        else{
          z += s[x];
          x = w[x];
        }
      }
    }
    return z;
  }
}
namespace sub6{
  const int lim = 4e5 + 1;
  Data up[25][7][lim];
  void init(){
    for(int i = 0; i < 25; i++){
      for(int j = 0; j < 7; j++){
        up[i][j][n] = Data(n, INF, 0);
      }
      for(int k = 0; k < n; k++){
        if(s[k] > (1 << i)){
          up[i][0][k] = Data(l[k], s[k] - 1, p[k]);
        }
        else{
          up[i][0][k] = Data(w[k], INF, s[k]);
        }
      }
      for(int j = 1; j < 7; j++){
        for(int k = 0; k < n; k++){
          up[i][j][k] = Data(k, INF, 0);
          for(int t = 0; t < 5; t++){
            minimize(up[i][j][k].need, up[i][j - 1][up[i][j][k].to].need - up[i][j][k].sum);
            up[i][j][k].sum += up[i][j - 1][up[i][j][k].to].sum;
            up[i][j][k].to = up[i][j - 1][up[i][j][k].to].to;
          }
        }
      }
    }
  }
  ll solve(int x, ll z){
    for(int i = 0; i < 25; i++){
      if(i == 24 || (1 << (i + 1)) > z){
        for(int j = 6; j > -1; j--){
          for(int t = 0; t < 130; t++){
            if(z <= up[i][j][x].need){
              z += up[i][j][x].sum;
              x = up[i][j][x].to;
            }
            else{
              break;
            }
          }
        }
        if(x == n){
          break;
        }
        if(z < s[x]){
          z += p[x];
          x = l[x];
        }
        else{
          z += s[x];
          x = w[x];
        }
      }
    }
    return z;
  }
}
void init(int _n, vector<int>_s, vector<int>_p, vector<int>_w, vector<int>_l){
  n = _n;
  swap(s, _s);
  swap(p, _p);
  swap(w, _w);
  swap(l, _l);
  if(n <= 50000 && max(*max_element(s.begin(), s.end()), *max_element(p.begin(), p.end())) <= 10000){
    subtask_id = 1;
  }
  else if(sub2::check_subtask()){
    subtask_id = 2;
    sub2::init();
  }
  else if(sub34::check_subtask()){
    subtask_id = 4;
    sub34::init();
  }
  else if(n <= 50000){
    subtask_id = 5;
    sub5::init();
  }
  else{
    subtask_id = 6;
    sub6::init();
  }
}
ll simulate(int x, int z){
  if(subtask_id == 1){
    return sub1::solve(x, z);
  }
  if(subtask_id == 2){
    return sub2::solve(x, z);
  }
  if(subtask_id == 4){
    return sub34::solve(x, z);
  }
  if(subtask_id == 5){
    return sub5::solve(x, z);
  }
  return sub6::solve(x, z);
}

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