oj.uz

답안 #790992

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
790992 2023-07-23T10:41:20 Z Trunkty 던전 (IOI21_dungeons) C++17
0 / 100
 63 ms 39920 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll

#include "dungeons.h"

ll n;
ll s[40005],p[40005],w[40005],l[40005];
ll jump[40005][41][41],sumi[40005][41][41],mini[40005][41][41];

void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L){
    // may need to expand to 41, 1e18, ll
    n = N;
    for(ll i=1;i<=n;i++){
        s[i] = S[i-1];
        p[i] = P[i-1];
        w[i] = W[i-1]+1;
        l[i] = L[i-1]+1;
    }
    for(ll k=0;k<=40;k++){
        jump[n+1][0][k] = n+1;
        for(ll i=1;i<=n;i++){
            if(s[i]<(1LL<<k)){
                jump[i][0][k] = w[i];
                sumi[i][0][k] = s[i];
                mini[i][0][k] = 1e18;
            }
            else if(s[i]>=(1LL<<(k+1LL))){
                jump[i][0][k] = l[i];
                sumi[i][0][k] = p[i];
                mini[i][0][k] = 1e18;
            }
            else{
                jump[i][0][k] = l[i];
                sumi[i][0][k] = p[i];
                mini[i][0][k] = s[i];
            }
        }
    }
    for(ll k=0;k<=40;k++){
        for(ll j=1;j<=40;j++){
            for(ll i=1;i<=n;i++){
                jump[i][j][k] = jump[jump[i][j-1][k]][j-1][k];
                sumi[i][j][k] = sumi[i][j-1][k]+sumi[jump[i][j-1][k]][j-1][k];
                mini[i][j][k] = min(mini[i][j-1][k],mini[jump[i][j-1][k]][j][k]-sumi[i][j-1][k]);
            }
        }
    }

}

ll simulate(int x, int z){
    x++;
    for(ll k=0;k<=40;k++){
        if(z<(1LL<<(k+1LL))){
            for(ll j=40;j>=0;j--){
                if(z+sumi[x][j][k]<(1LL<<(k+1LL)) and z<mini[x][j][k] and jump[x][j][k]!=n+1){
                    z += sumi[x][j][k];
                    x = jump[x][j][k];
                }
            }
            if(z>=s[x]){
                z += s[x];
                x = w[x];
            }
            else{
                z += p[x];
                x = l[x];
            }
            if(x==n+1){
                break;
            }
        }
    }
	return z;
}

Subtask #1
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 63 ms 39892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 39920 KB Output is correct
2 Runtime error 37 ms 5460 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 39920 KB Output is correct
2 Runtime error 37 ms 5460 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 39920 KB Output is correct
2 Runtime error 37 ms 5460 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 63 ms 39892 KB Output isn't correct
2 Halted 0 ms 0 KB -