답안 #990929

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
990929 2024-05-31T20:11:34 Z AdamGS 던전 (IOI21_dungeons) C++17
0 / 100
10 ms 25160 KB
#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=5e4+7, LG=24;
ll nxt[LIM][LG][LG], sum[LIM][LG][LG], ile[LIM][LG][LG], nxt2[LIM][LG], sum2[LIM][LG], S[LIM], P[LIM], W[LIM], L[LIM], n;
void init(int _n, vector<int>_s, vector<int>_p, vector<int>_w, vector<int>_l) {
  n=_n;
  rep(i, n) {
    S[i]=_s[i];
    P[i]=_p[i];
    W[i]=_w[i];
    L[i]=_l[i];
  }
  rep(i, LG) {
    nxt[n][i][0]=n;
    rep(j, n) {
      if(S[j]>=(1<<i)) {
        nxt[j][i][0]=L[j];
        sum[j][i][0]=P[j];
        ile[j][i][0]=S[j];
      } else {
        nxt[j][i][0]=W[j];
        sum[j][i][0]=S[j];
        ile[j][i][0]=(1<<(i+1))-S[j];
      }
    }
    for(int l=1; l<LG; ++l) {
      rep(j, n+1) {
        nxt[j][i][l]=nxt[nxt[j][i][l-1]][i][l-1];
        sum[j][i][l]=sum[j][i][l-1]+sum[nxt[i][j][l-1]][i][l-1];
        ile[j][i][l]=min(ile[j][i][l-1], ile[nxt[i][j][l-1]][i][l-1]-sum[j][i][l-1]);
      }
    }
  }
  nxt2[n][0]=n;
  rep(i, n) {
    nxt2[i][0]=W[i];
    sum2[i][0]=S[i];
  }
  for(int j=1; j<LG; ++j) {
    rep(i, n+1) {
      nxt2[i][j]=nxt2[nxt2[i][j-1]][j-1];
      sum2[i][j]=sum2[nxt2[i][j-1]][j-1]+sum2[i][j-1];
    }
  }
  return;
}
ll simulate(int x, int _z) {
  ll z=_z;
  rep(i, LG) if(z<(1ll<<(ll)(i+1))) {
    for(int j=LG-1; j>=0; --j) if(nxt[x][i][j]<n && ile[x][i][j]>z) {
      z+=sum[x][i][j];
      x=nxt[x][i][j];
    }
    if(z>=S[x]) {
      z+=S[x];
      x=W[x];
    } else {
      z+=P[x];
      x=L[x];
    }
    if(x==n) return z;
  }
  for(int i=LG-1; i>=0; --i) if(nxt2[x][i]<n) {
    z+=sum2[x][i];
    x=nxt2[x][i];
  }
  z+=sum2[x][0];
  x=nxt2[x][0];
  return z;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Incorrect 1 ms 10588 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 24924 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 25160 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 25160 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 25160 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 24924 KB Output isn't correct
2 Halted 0 ms 0 KB -