oj.uz

답안 #1016700

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1016700 2024-07-08T10:36:48 Z JakobZorz 던전 (IOI21_dungeons) C++17
63 / 100
 3644 ms 2097156 KB 
#include"dungeons.h"
#include<vector>
#include<iostream>
typedef long long ll;
using namespace std;
 
int n;
 
struct Dungeon{
    vector<int>nxt1; // win
    vector<int>nxt2; // lose
    vector<ll>st1;  // strength
    vector<ll>st2;  // gain on losing
    vector<vector<int>>jmp; // where to jump?
    vector<vector<ll>>gain; // strength gain of that jump
    vector<vector<ll>>win;  // strength requirement to win in that jump
    int pw;
    ll thres=0;
    
    Dungeon(int n):nxt1(n),nxt2(n),st1(n),st2(n){}
    Dungeon()=default;
    
    void setup(){
        jmp=vector<vector<int>>(n+1,vector<int>(pw));
        gain=vector<vector<ll>>(n+1,vector<ll>(pw));
        win=vector<vector<ll>>(n+1,vector<ll>(pw));
        for(int p=0;p<pw;p++)
            jmp[n][p]=n;
        
        for(int i=0;i<n;i++){
            jmp[i][0]=nxt2[i];
            gain[i][0]=st2[i];
            win[i][0]=st1[i];
        }
            
        for(int p=1;p<pw;p++){
            for(int i=0;i<n;i++){
                jmp[i][p]=jmp[jmp[i][p-1]][p-1];
                gain[i][p]=gain[i][p-1]+gain[jmp[i][p-1]][p-1];
                if(win[jmp[i][p-1]][p-1]==1e18)
                    win[i][p]=win[i][p-1];
                else
                    win[i][p]=max(0LL,min(win[i][p-1],win[jmp[i][p-1]][p-1]-gain[i][p-1]));
            }
        }
    }
    
    // simulate until it either reaches n-th node, wins, or strength>=thres
    pair<int,ll>simulate(int x,ll st){
        for(int p=pw;p>=0;p--){
            if(jmp[x][p]!=n&&(win[x][p]>st||win[x][p]==1e18)&&st+gain[x][p]<thres){
                st+=gain[x][p];
                x=jmp[x][p];
            }
        }
        // do 1 more jump
        if(st>=st1[x]){
            st+=st1[x];
            x=nxt1[x];
        }else{
            st+=st2[x];
            x=nxt2[x];
        }
        return{x,st};
    }
};
 
Dungeon dun[25];
 
void init(int N,vector<int>s,vector<int>p,vector<int>w,vector<int>l){
    n=N;
    
    for(int pw=0;pw<25;pw++){
        dun[pw]=Dungeon(n);
        dun[pw].thres=2LL<<pw;
        dun[pw].pw=pw+1;
        for(int i=0;i<n;i++){
            if(s[i]<=1<<pw){
                dun[pw].nxt1[i]=0;
                dun[pw].nxt2[i]=w[i];
                dun[pw].st1[i]=1e18;
                dun[pw].st2[i]=s[i];
            }else if(s[i]>=2<<pw){
                dun[pw].nxt1[i]=0;
                dun[pw].nxt2[i]=l[i];
                dun[pw].st1[i]=1e18;
                dun[pw].st2[i]=p[i];
            }else{
                dun[pw].nxt1[i]=w[i];
                dun[pw].nxt2[i]=l[i];
                dun[pw].st1[i]=s[i];
                dun[pw].st2[i]=p[i];
            }
        }
    }
    dun[24].thres=1e18;
    for(int pw=0;pw<25;pw++)
        dun[pw].setup();
}
 
ll simulate(int x,int z){
    ll st=z;
    
    for(int p=0;p<25;p++){
        while(x!=n&&st<2LL<<p){
            auto r=dun[p].simulate(x,st);
            x=r.first;
            st=r.second;
        }
    }
    
    return st;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 17 ms 19804 KB Output is correct
4 Correct 479 ms 487252 KB Output is correct
5 Correct 18 ms 19804 KB Output is correct
6 Correct 484 ms 487160 KB Output is correct

Subtask #2
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 10076 KB Output is correct
2 Runtime error 2080 ms 2097156 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 10076 KB Output is correct
2 Correct 578 ms 487372 KB Output is correct
3 Correct 558 ms 487292 KB Output is correct
4 Correct 499 ms 488540 KB Output is correct
5 Correct 507 ms 488516 KB Output is correct
6 Correct 839 ms 488596 KB Output is correct
7 Correct 837 ms 488528 KB Output is correct
8 Correct 1075 ms 488272 KB Output is correct
9 Correct 508 ms 488296 KB Output is correct
10 Correct 982 ms 488276 KB Output is correct
11 Correct 1199 ms 488532 KB Output is correct
12 Correct 3644 ms 488752 KB Output is correct
13 Correct 3622 ms 488528 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 10076 KB Output is correct
2 Correct 578 ms 487372 KB Output is correct
3 Correct 558 ms 487292 KB Output is correct
4 Correct 499 ms 488540 KB Output is correct
5 Correct 507 ms 488516 KB Output is correct
6 Correct 839 ms 488596 KB Output is correct
7 Correct 837 ms 488528 KB Output is correct
8 Correct 1075 ms 488272 KB Output is correct
9 Correct 508 ms 488296 KB Output is correct
10 Correct 982 ms 488276 KB Output is correct
11 Correct 1199 ms 488532 KB Output is correct
12 Correct 3644 ms 488752 KB Output is correct
13 Correct 3622 ms 488528 KB Output is correct
14 Correct 9 ms 10076 KB Output is correct
15 Correct 518 ms 488784 KB Output is correct
16 Correct 570 ms 488972 KB Output is correct
17 Correct 589 ms 488568 KB Output is correct
18 Correct 615 ms 488572 KB Output is correct
19 Correct 753 ms 488532 KB Output is correct
20 Correct 821 ms 488276 KB Output is correct
21 Correct 929 ms 488528 KB Output is correct
22 Correct 1048 ms 488532 KB Output is correct
23 Correct 1912 ms 488532 KB Output is correct
24 Correct 1898 ms 488704 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 10076 KB Output is correct
2 Correct 578 ms 487372 KB Output is correct
3 Correct 558 ms 487292 KB Output is correct
4 Correct 499 ms 488540 KB Output is correct
5 Correct 507 ms 488516 KB Output is correct
6 Correct 839 ms 488596 KB Output is correct
7 Correct 837 ms 488528 KB Output is correct
8 Correct 1075 ms 488272 KB Output is correct
9 Correct 508 ms 488296 KB Output is correct
10 Correct 982 ms 488276 KB Output is correct
11 Correct 1199 ms 488532 KB Output is correct
12 Correct 3644 ms 488752 KB Output is correct
13 Correct 3622 ms 488528 KB Output is correct
14 Correct 9 ms 10076 KB Output is correct
15 Correct 518 ms 488784 KB Output is correct
16 Correct 570 ms 488972 KB Output is correct
17 Correct 589 ms 488568 KB Output is correct
18 Correct 615 ms 488572 KB Output is correct
19 Correct 753 ms 488532 KB Output is correct
20 Correct 821 ms 488276 KB Output is correct
21 Correct 929 ms 488528 KB Output is correct
22 Correct 1048 ms 488532 KB Output is correct
23 Correct 1912 ms 488532 KB Output is correct
24 Correct 1898 ms 488704 KB Output is correct
25 Correct 523 ms 487876 KB Output is correct
26 Correct 626 ms 489088 KB Output is correct
27 Correct 501 ms 488404 KB Output is correct
28 Correct 502 ms 488500 KB Output is correct
29 Correct 764 ms 488800 KB Output is correct
30 Correct 888 ms 488524 KB Output is correct
31 Correct 1028 ms 488260 KB Output is correct
32 Correct 1124 ms 488544 KB Output is correct
33 Correct 768 ms 488532 KB Output is correct
34 Correct 1199 ms 488404 KB Output is correct
35 Correct 1010 ms 488416 KB Output is correct

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 10076 KB Output is correct
2 Runtime error 2080 ms 2097156 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -