Submission #1021096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021096		awu	Dungeons Game (IOI21_dungeons)	C++17	Compilation error	0 ms	0 KiB

dungeons

#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

#define int long long
#define ll long long
// #define double long double
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define debug(...) [&](decltype(__VA_ARGS__) _x){cerr << #__VA_ARGS__ << " = " << _x << endl; return _x;}(__VA_ARGS__)
using pii = pair<int, int>;
const ll inf = 1ll << 60;
// const int inf = 1 << 30;

template <typename T, typename U>
ostream& operator<<(ostream& out, pair<T, U> p) {
  out << "(" << p.f << ", " << p.s << ")";
  return out;
}
template<typename T>
typename enable_if<!is_same<T, const char *>::value && !is_same<T, string>::value, ostream&>::type operator<<(ostream& out, T o) {
  out << "{";
  int g = o.size();
  for(auto i : o) out << i << (--g ? ", " : "");
  out << "}";
  return out;
}
// void my_assert(bool b) {
//   if(!b) {
//     cerr << "Assertion failed" << endl;
//     *((volatile int*)0);
//   }
// }
// #undef assert
// #define assert my_assert

int millis() {
  return chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count();
}
int pt = 0;
int start_time;
void pstart() {
  start_time = millis();
}
void pend() {
  pt += millis() - start_time;
}

int n;
vector<signed> s, p, w, l;
vector<vector<vector<int>>> jmp, mx;
vector<vector<vector<int>>> prec; // mx is exc

int nk = 25;
int jl = 20;

void init(signed N, vector<signed> S, vector<signed> P, vector<signed> W, vector<signed> L) {
  pstart();
  n = N;
  s = S;
  p = P;
  w = W;
  l = L;
  jmp = mx = vector<vector<vector<int>>>(nk, vector<vector<int>>(n + 1, vector<int>(jl)));
  prec = vector<vector<vector<int>>>(nk, vector<vector<int>>(n + 1, vector<int>(jl)));
  for(int i = 0; i < nk; i++) {
    for(int j = 0; j < n; j++) {
      if((1 << i) >= s[j]) {
        jmp[i][j][0] = w[j];
        prec[i][j][0] = s[j];
        mx[i][j][0] = inf;
      } else {
        jmp[i][j][0] = l[j];
        prec[i][j][0] = p[j];
        mx[i][j][0] = s[j];
      }
    }
    fill(all(jmp[i][n]), n);
    fill(all(mx[i][n]), inf);
    for(int k = 1; k < jl; k++) {
      for(int j = 0; j < n; j++) {
        jmp[i][j][k] = jmp[i][jmp[i][j][k - 1]][k - 1];
        prec[i][j][k] = prec[i][j][k - 1] + prec[i][jmp[i][j][k - 1]][k - 1];
        mx[i][j][k] = min(mx[i][j][k - 1], (int)max(0ll, mx[i][jmp[i][j][k - 1]][k - 1] - prec[i][j][k - 1]));
      }
    }
  }
  pend();
  assert(pt < 2000);
}

int fastlog2(int x) {
  return 63 - __builtin_clzll(x);
}

int simulate(signed x, signed Z) {
  int z = Z;
  int li = -1;
  int icnt = 0;
  while(x != n) {
    icnt++;
    // assert(icnt < 40);
    if(z >= s[x]) {
      z += s[x];
      x = w[x];
    } else {
      z += p[x];
      x = l[x];
    }
    int i = fastlog2(z);
    assert(z >= 1e7 || i > li);
    li = i;
    i = min(i, nk - 1);
    for(int k = jl - 1; k >= 0; k--) {
      if(z < mx[i][x][k]) {
        z += prec[i][x][k];
        x = jmp[i][x][k];
        if(x == n) break;
      }
    }
    // assert(x == n || z >= s[x]);
  }
  return z;
}

signed main() {
  int n, q; cin >> n >> q;
  vector<signed> s(n), p(n), w(n), l(n);
  for(int i = 0; i < n; i++) cin >> s[i];
  for(int i = 0; i < n; i++) cin >> p[i];
  for(int i = 0; i < n; i++) cin >> w[i];
  for(int i = 0; i < n; i++) cin >> l[i];
  init(n, s, p, w, l);
  while(q--) {
    int x, z; cin >> x >> z;
    cout << simulate(x, z) << endl;
  }
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccQLfBab.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cclqVspa.o:dungeons.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status