oj.uz

답안 #961557

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
961557 2024-04-12T08:03:06 Z Warinchai 던전 (IOI21_dungeons) C++17
13 / 100
 1592 ms 1305768 KB 
#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
int lift[50][50][50005];
int mn[50][50][50005];
long long dis[50][50][50005];
long long inf=1e18+7;
int N;
vector<int>W;
vector<int>S;
vector<int>L;
vector<int>P;
int X=0;
void init(int n,vector<int> s,vector<int> p,vector<int> w,vector<int> l) {
    N=n;
    S=s;
    W=w;
    L=l;
    P=p;
    //cerr<<"work\n";
    for(int i=0;i<=45;i++){
        int st=(1<<(i-1))+1;
        int en=(1<<i);
        for(int j=0;j<n;j++){
            if(s[j]>en)lift[i][0][j]=l[j],mn[i][0][j]=inf,dis[i][0][j]=p[j];
            else if(s[j]>=st)lift[i][0][j]=l[j],mn[i][0][j]=s[j],dis[i][0][j]=p[j];
            else lift[i][0][j]=w[j],mn[i][0][j]=inf,dis[i][0][j]=s[j];
        }
        lift[i][0][n]=n;
        mn[i][0][n]=0;
        for(int j=1;j<=25;j++){
            for(int k=0;k<=n;k++){
                //cerr<<i<<" "<<j<<" "<<k<<"\n";
                lift[i][j][k]=lift[i][j-1][lift[i][j-1][k]];
                dis[i][j][k]=dis[i][j-1][k]+dis[i][j-1][lift[i][j-1][k]];
                X=mn[i][j-1][lift[i][j-1][k]]-dis[i][j-1][k];
                if(dis[i][j-1][k]>mn[i][j-1][lift[i][j-1][k]])mn[i][j][k]=0;
                else mn[i][j][k]=min(mn[i][j-1][k],X);
            }
        }
    }
    //cerr<<"work\n";
	return;
}
 
long long simulate(int x, int z) {
    //cerr<<"work\n";
    long long c=0,lv=0;
    long long pow=z;
    while(x>(1<<c)){
        lv=c;
        c++;
    }
    //cerr<<x<<"\n";
    //cerr<<lv<<"\n";
    while(1){
        //cerr<<x<<" "<<pow<<"\n";
        if(lv==25)return pow+dis[lv][25][x];
        for(int i=25;i>=0;i--){
            //cerr<<i<<" "<<lv<<" "<<x<<"\n";
            if(pow<mn[lv][i][x]&&pow+dis[lv][i][x]<=(1<<lv))pow+=dis[lv][i][x],x=lift[lv][i][x];
        }
        //cerr<<x<<" "<<pow<<"\n\n";
        if(x==N)break;
        if(pow>=S[x])pow+=S[x],x=W[x];
        else {
            pow+=P[x];
            x=L[x];
        }
        lv++;
    }
	return pow;
}

Subtask #1
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 155 ms 458304 KB Output is correct
2 Correct 52 ms 458076 KB Output is correct
3 Correct 66 ms 483136 KB Output is correct
4 Correct 434 ms 1044308 KB Output is correct
5 Incorrect 75 ms 496976 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 487508 KB Output is correct
2 Incorrect 1592 ms 1305768 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 487584 KB Output is correct
2 Correct 538 ms 1046628 KB Output is correct
3 Correct 566 ms 1046876 KB Output is correct
4 Correct 581 ms 1047728 KB Output is correct
5 Correct 578 ms 1047624 KB Output is correct
6 Correct 616 ms 1049720 KB Output is correct
7 Correct 603 ms 1047888 KB Output is correct
8 Correct 577 ms 1047612 KB Output is correct
9 Correct 477 ms 1047396 KB Output is correct
10 Correct 568 ms 1047372 KB Output is correct
11 Correct 662 ms 1047716 KB Output is correct
12 Correct 804 ms 1047888 KB Output is correct
13 Correct 643 ms 1047900 KB Output is correct

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 487584 KB Output is correct
2 Correct 538 ms 1046628 KB Output is correct
3 Correct 566 ms 1046876 KB Output is correct
4 Correct 581 ms 1047728 KB Output is correct
5 Correct 578 ms 1047624 KB Output is correct
6 Correct 616 ms 1049720 KB Output is correct
7 Correct 603 ms 1047888 KB Output is correct
8 Correct 577 ms 1047612 KB Output is correct
9 Correct 477 ms 1047396 KB Output is correct
10 Correct 568 ms 1047372 KB Output is correct
11 Correct 662 ms 1047716 KB Output is correct
12 Correct 804 ms 1047888 KB Output is correct
13 Correct 643 ms 1047900 KB Output is correct
14 Incorrect 61 ms 487508 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 487584 KB Output is correct
2 Correct 538 ms 1046628 KB Output is correct
3 Correct 566 ms 1046876 KB Output is correct
4 Correct 581 ms 1047728 KB Output is correct
5 Correct 578 ms 1047624 KB Output is correct
6 Correct 616 ms 1049720 KB Output is correct
7 Correct 603 ms 1047888 KB Output is correct
8 Correct 577 ms 1047612 KB Output is correct
9 Correct 477 ms 1047396 KB Output is correct
10 Correct 568 ms 1047372 KB Output is correct
11 Correct 662 ms 1047716 KB Output is correct
12 Correct 804 ms 1047888 KB Output is correct
13 Correct 643 ms 1047900 KB Output is correct
14 Incorrect 61 ms 487508 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 487508 KB Output is correct
2 Incorrect 1592 ms 1305768 KB Output isn't correct
3 Halted 0 ms 0 KB -