oj.uz

답안 #441331

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
441331 2021-07-05T00:12:44 Z Dormi 던전 (IOI21_dungeons) C++17
100 / 100
 3301 ms 1788964 KB 
#include "bits/stdc++.h"
#include "dungeons.h"
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
int sz(const T &a){return int(a.size());}
const int MN=4e5+1,B=11,ML=8;
vector<vector<pair<int,pair<ll,int>>>> lift[ML];//minimum to get to the lifted node and win against any >=pc[i]
int pc[ML],n,win[MN],lose[MN],strength[MN],lgain[MN];
void init(int N, vector<int> s, vector<int> p, vector<int> w, vector<int> l){
    n=N;
    pc[0]=1;
    win[n]=n,lose[n]=n,strength[n]=0,lgain[n]=0;
    for(int i=0;i<n;i++)win[i]=w[i],lose[i]=l[i],strength[i]=s[i],lgain[i]=p[i];
    for(int i=0;i<ML;i++){
        if(i)pc[i]=pc[i-1]*B;
        lift[i].resize(__lg(max(0,int(1e7)-pc[i])+n)+1,vector<pair<int,pair<ll,int>>>(n+1));
        lift[i][0][n]={n,{0,INT_MAX}};
        for(int j=0;j<n;j++){
            if(s[j]>=pc[i])lift[i][0][j]={l[j],{p[j],s[j]}};
            else lift[i][0][j]={w[j],{s[j],INT_MAX}};
        }
        for(int j=1;j<sz(lift[i]);j++){
            for(int k=0;k<=n;k++){
                lift[i][j][k].first=lift[i][j-1][lift[i][j-1][k].first].first;
                lift[i][j][k].second.first=lift[i][j-1][k].second.first+lift[i][j-1][lift[i][j-1][k].first].second.first;
                lift[i][j][k].second.second=min(lift[i][j-1][k].second.second,(lift[i][j-1][lift[i][j-1][k].first].second.second==INT_MAX?INT_MAX:max(0,int(lift[i][j-1][lift[i][j-1][k].first].second.second-min(lift[i][j-1][k].second.first,ll(1e7))))));
            }
        }
    }
}

ll simulate(int cur, int z){
    ll str=z;
    while(cur!=n){
        int level=upper_bound(pc,pc+ML,str)-pc-1;
        while(cur!=n&&str<(level==ML-1?LLONG_MAX:pc[level+1])){
            for(int i=sz(lift[level])-1;i>=0;i--){
                if(lift[level][i][cur].second.second>str||lift[level][i][cur].second.second==INT_MAX){
                    str+=lift[level][i][cur].second.first;
                    cur=lift[level][i][cur].first;
                }
            }
            if(str>=strength[cur]){
                str+=strength[cur];
                cur=win[cur];
            }
            else{
                str+=lgain[cur];
                cur=lose[cur];
            }
        }
    }
    return str;
}


//int main(){
//    cin.tie(NULL);
//    ios_base::sync_with_stdio(false);
//
//    return 0;
//}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 7 ms 8736 KB Output is correct
4 Correct 176 ms 218668 KB Output is correct
5 Correct 7 ms 8780 KB Output is correct
6 Correct 172 ms 218668 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4556 KB Output is correct
2 Correct 1480 ms 1786248 KB Output is correct
3 Correct 1423 ms 1786396 KB Output is correct
4 Correct 1431 ms 1786556 KB Output is correct
5 Correct 1529 ms 1786316 KB Output is correct
6 Correct 1521 ms 1786456 KB Output is correct
7 Correct 1522 ms 1786340 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4556 KB Output is correct
2 Correct 334 ms 219440 KB Output is correct
3 Correct 261 ms 219456 KB Output is correct
4 Correct 192 ms 219456 KB Output is correct
5 Correct 191 ms 219572 KB Output is correct
6 Correct 336 ms 219416 KB Output is correct
7 Correct 296 ms 219440 KB Output is correct
8 Correct 210 ms 219432 KB Output is correct
9 Correct 233 ms 219524 KB Output is correct
10 Correct 219 ms 219444 KB Output is correct
11 Correct 223 ms 219440 KB Output is correct
12 Correct 328 ms 219448 KB Output is correct
13 Correct 275 ms 219504 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4556 KB Output is correct
2 Correct 334 ms 219440 KB Output is correct
3 Correct 261 ms 219456 KB Output is correct
4 Correct 192 ms 219456 KB Output is correct
5 Correct 191 ms 219572 KB Output is correct
6 Correct 336 ms 219416 KB Output is correct
7 Correct 296 ms 219440 KB Output is correct
8 Correct 210 ms 219432 KB Output is correct
9 Correct 233 ms 219524 KB Output is correct
10 Correct 219 ms 219444 KB Output is correct
11 Correct 223 ms 219440 KB Output is correct
12 Correct 328 ms 219448 KB Output is correct
13 Correct 275 ms 219504 KB Output is correct
14 Correct 4 ms 4556 KB Output is correct
15 Correct 224 ms 219440 KB Output is correct
16 Correct 285 ms 219456 KB Output is correct
17 Correct 201 ms 219440 KB Output is correct
18 Correct 215 ms 219452 KB Output is correct
19 Correct 316 ms 219436 KB Output is correct
20 Correct 259 ms 219456 KB Output is correct
21 Correct 251 ms 219456 KB Output is correct
22 Correct 283 ms 219452 KB Output is correct
23 Correct 233 ms 219440 KB Output is correct
24 Correct 334 ms 219456 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4556 KB Output is correct
2 Correct 334 ms 219440 KB Output is correct
3 Correct 261 ms 219456 KB Output is correct
4 Correct 192 ms 219456 KB Output is correct
5 Correct 191 ms 219572 KB Output is correct
6 Correct 336 ms 219416 KB Output is correct
7 Correct 296 ms 219440 KB Output is correct
8 Correct 210 ms 219432 KB Output is correct
9 Correct 233 ms 219524 KB Output is correct
10 Correct 219 ms 219444 KB Output is correct
11 Correct 223 ms 219440 KB Output is correct
12 Correct 328 ms 219448 KB Output is correct
13 Correct 275 ms 219504 KB Output is correct
14 Correct 4 ms 4556 KB Output is correct
15 Correct 224 ms 219440 KB Output is correct
16 Correct 285 ms 219456 KB Output is correct
17 Correct 201 ms 219440 KB Output is correct
18 Correct 215 ms 219452 KB Output is correct
19 Correct 316 ms 219436 KB Output is correct
20 Correct 259 ms 219456 KB Output is correct
21 Correct 251 ms 219456 KB Output is correct
22 Correct 283 ms 219452 KB Output is correct
23 Correct 233 ms 219440 KB Output is correct
24 Correct 334 ms 219456 KB Output is correct
25 Correct 184 ms 218688 KB Output is correct
26 Correct 285 ms 219492 KB Output is correct
27 Correct 234 ms 219400 KB Output is correct
28 Correct 229 ms 219460 KB Output is correct
29 Correct 304 ms 219568 KB Output is correct
30 Correct 266 ms 219420 KB Output is correct
31 Correct 267 ms 219592 KB Output is correct
32 Correct 380 ms 219412 KB Output is correct
33 Correct 1014 ms 219440 KB Output is correct
34 Correct 1515 ms 219312 KB Output is correct
35 Correct 789 ms 219440 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 4556 KB Output is correct
2 Correct 1480 ms 1786248 KB Output is correct
3 Correct 1423 ms 1786396 KB Output is correct
4 Correct 1431 ms 1786556 KB Output is correct
5 Correct 1529 ms 1786316 KB Output is correct
6 Correct 1521 ms 1786456 KB Output is correct
7 Correct 1522 ms 1786340 KB Output is correct
8 Correct 4 ms 4556 KB Output is correct
9 Correct 334 ms 219440 KB Output is correct
10 Correct 261 ms 219456 KB Output is correct
11 Correct 192 ms 219456 KB Output is correct
12 Correct 191 ms 219572 KB Output is correct
13 Correct 336 ms 219416 KB Output is correct
14 Correct 296 ms 219440 KB Output is correct
15 Correct 210 ms 219432 KB Output is correct
16 Correct 233 ms 219524 KB Output is correct
17 Correct 219 ms 219444 KB Output is correct
18 Correct 223 ms 219440 KB Output is correct
19 Correct 328 ms 219448 KB Output is correct
20 Correct 275 ms 219504 KB Output is correct
21 Correct 4 ms 4556 KB Output is correct
22 Correct 224 ms 219440 KB Output is correct
23 Correct 285 ms 219456 KB Output is correct
24 Correct 201 ms 219440 KB Output is correct
25 Correct 215 ms 219452 KB Output is correct
26 Correct 316 ms 219436 KB Output is correct
27 Correct 259 ms 219456 KB Output is correct
28 Correct 251 ms 219456 KB Output is correct
29 Correct 283 ms 219452 KB Output is correct
30 Correct 233 ms 219440 KB Output is correct
31 Correct 334 ms 219456 KB Output is correct
32 Correct 184 ms 218688 KB Output is correct
33 Correct 285 ms 219492 KB Output is correct
34 Correct 234 ms 219400 KB Output is correct
35 Correct 229 ms 219460 KB Output is correct
36 Correct 304 ms 219568 KB Output is correct
37 Correct 266 ms 219420 KB Output is correct
38 Correct 267 ms 219592 KB Output is correct
39 Correct 380 ms 219412 KB Output is correct
40 Correct 1014 ms 219440 KB Output is correct
41 Correct 1515 ms 219312 KB Output is correct
42 Correct 789 ms 219440 KB Output is correct
43 Correct 1 ms 332 KB Output is correct
44 Correct 4 ms 4556 KB Output is correct
45 Correct 1848 ms 1788764 KB Output is correct
46 Correct 1566 ms 1788692 KB Output is correct
47 Correct 1518 ms 1788880 KB Output is correct
48 Correct 1535 ms 1788800 KB Output is correct
49 Correct 1903 ms 1788692 KB Output is correct
50 Correct 1492 ms 1788724 KB Output is correct
51 Correct 1482 ms 1788776 KB Output is correct
52 Correct 1489 ms 1788812 KB Output is correct
53 Correct 2757 ms 1788788 KB Output is correct
54 Correct 2784 ms 1788608 KB Output is correct
55 Correct 3213 ms 1788964 KB Output is correct
56 Correct 2969 ms 1788728 KB Output is correct
57 Correct 2985 ms 1788832 KB Output is correct
58 Correct 3215 ms 1788884 KB Output is correct
59 Correct 3301 ms 1788828 KB Output is correct
60 Correct 2790 ms 1788780 KB Output is correct
61 Correct 2680 ms 1788692 KB Output is correct