oj.uz

Submission #896251

# Submission time Handle Problem Language Result Execution time Memory
896251 2024-01-01T05:37:07 Z Sir_Ahmed_Imran Dungeons Game (IOI21_dungeons) C++17
50 / 100
 7000 ms 596136 KB 
                              ///~~~LOTA~~~///
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long 
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define N 400001
ll n;
ll l[N][31];
ll w[N][31];
ll sl[N][31];
ll sw[N][31];
ll rw[N][31];
ll rl[N][31];
void init(int m,vector<int> s,vector<int> p,vector<int> W,vector<int> L){
    n=m;
    w[n][0]=n;
    rw[n][0]=1e18;
    for(int i=0;i<n;i++){
        l[i][0]=L[i];
        w[i][0]=W[i];
        sl[i][0]=p[i];
        sw[i][0]=s[i];
        rl[i][0]=s[i]+p[i];
        rw[i][0]=s[i]+s[i];
    }
    for(int j=0;j<30;j++){
        for(int i=0;i<=n;i++){
            l[i][j+1]=l[l[i][j]][j];
            w[i][j+1]=w[w[i][j]][j];
            sl[i][j+1]=sl[i][j]+sl[l[i][j]][j];
            sw[i][j+1]=sw[i][j]+sw[w[i][j]][j];
            rl[i][j+1]=min(rl[l[i][j]][j],rl[i][j]+sl[l[i][j]][j]);
            rw[i][j+1]=max(rw[w[i][j]][j],rw[i][j]+sw[w[i][j]][j]);
        }
    }
}
ll simulate(int x,int z){
    int t=0;
    ll p=x;
    ll q=z;
    while(p!=n){
        if(t==1){
            for(int j=30;j>=0;j--){
                if(rw[p][j]<=sw[p][j]+q){
                    q+=sw[p][j];
                    p=w[p][j];
                }
            }
        }
        else{
            for(int j=30;j>=0;j--){
                if(rl[p][j]>sl[p][j]+q){
                    q+=sl[p][j];
                    p=l[p][j];
                }
            }
        }
        t=(t+1)%2;
    }
    return q;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 3 ms 14936 KB Output is correct
4 Correct 82 ms 86248 KB Output is correct
5 Correct 3 ms 14940 KB Output is correct
6 Correct 75 ms 86308 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 750 ms 595912 KB Output is correct
3 Correct 681 ms 596124 KB Output is correct
4 Correct 702 ms 596136 KB Output is correct
5 Correct 656 ms 596132 KB Output is correct
6 Correct 733 ms 596052 KB Output is correct
7 Correct 637 ms 596052 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 116 ms 87268 KB Output is correct
3 Correct 129 ms 87096 KB Output is correct
4 Correct 113 ms 86876 KB Output is correct
5 Correct 114 ms 87004 KB Output is correct
6 Correct 104 ms 87252 KB Output is correct
7 Correct 96 ms 86872 KB Output is correct
8 Correct 114 ms 87056 KB Output is correct
9 Correct 105 ms 87088 KB Output is correct
10 Correct 114 ms 86876 KB Output is correct
11 Correct 115 ms 87048 KB Output is correct
12 Correct 191 ms 86880 KB Output is correct
13 Correct 166 ms 87088 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 116 ms 87268 KB Output is correct
3 Correct 129 ms 87096 KB Output is correct
4 Correct 113 ms 86876 KB Output is correct
5 Correct 114 ms 87004 KB Output is correct
6 Correct 104 ms 87252 KB Output is correct
7 Correct 96 ms 86872 KB Output is correct
8 Correct 114 ms 87056 KB Output is correct
9 Correct 105 ms 87088 KB Output is correct
10 Correct 114 ms 86876 KB Output is correct
11 Correct 115 ms 87048 KB Output is correct
12 Correct 191 ms 86880 KB Output is correct
13 Correct 166 ms 87088 KB Output is correct
14 Correct 2 ms 13144 KB Output is correct
15 Correct 203 ms 87020 KB Output is correct
16 Correct 117 ms 87092 KB Output is correct
17 Correct 123 ms 87092 KB Output is correct
18 Correct 121 ms 87088 KB Output is correct
19 Correct 106 ms 86876 KB Output is correct
20 Correct 139 ms 86876 KB Output is correct
21 Correct 130 ms 87132 KB Output is correct
22 Execution timed out 7094 ms 86864 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 116 ms 87268 KB Output is correct
3 Correct 129 ms 87096 KB Output is correct
4 Correct 113 ms 86876 KB Output is correct
5 Correct 114 ms 87004 KB Output is correct
6 Correct 104 ms 87252 KB Output is correct
7 Correct 96 ms 86872 KB Output is correct
8 Correct 114 ms 87056 KB Output is correct
9 Correct 105 ms 87088 KB Output is correct
10 Correct 114 ms 86876 KB Output is correct
11 Correct 115 ms 87048 KB Output is correct
12 Correct 191 ms 86880 KB Output is correct
13 Correct 166 ms 87088 KB Output is correct
14 Correct 2 ms 13144 KB Output is correct
15 Correct 203 ms 87020 KB Output is correct
16 Correct 117 ms 87092 KB Output is correct
17 Correct 123 ms 87092 KB Output is correct
18 Correct 121 ms 87088 KB Output is correct
19 Correct 106 ms 86876 KB Output is correct
20 Correct 139 ms 86876 KB Output is correct
21 Correct 130 ms 87132 KB Output is correct
22 Execution timed out 7094 ms 86864 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12892 KB Output is correct
2 Correct 750 ms 595912 KB Output is correct
3 Correct 681 ms 596124 KB Output is correct
4 Correct 702 ms 596136 KB Output is correct
5 Correct 656 ms 596132 KB Output is correct
6 Correct 733 ms 596052 KB Output is correct
7 Correct 637 ms 596052 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 116 ms 87268 KB Output is correct
10 Correct 129 ms 87096 KB Output is correct
11 Correct 113 ms 86876 KB Output is correct
12 Correct 114 ms 87004 KB Output is correct
13 Correct 104 ms 87252 KB Output is correct
14 Correct 96 ms 86872 KB Output is correct
15 Correct 114 ms 87056 KB Output is correct
16 Correct 105 ms 87088 KB Output is correct
17 Correct 114 ms 86876 KB Output is correct
18 Correct 115 ms 87048 KB Output is correct
19 Correct 191 ms 86880 KB Output is correct
20 Correct 166 ms 87088 KB Output is correct
21 Correct 2 ms 13144 KB Output is correct
22 Correct 203 ms 87020 KB Output is correct
23 Correct 117 ms 87092 KB Output is correct
24 Correct 123 ms 87092 KB Output is correct
25 Correct 121 ms 87088 KB Output is correct
26 Correct 106 ms 86876 KB Output is correct
27 Correct 139 ms 86876 KB Output is correct
28 Correct 130 ms 87132 KB Output is correct
29 Execution timed out 7094 ms 86864 KB Time limit exceeded
30 Halted 0 ms 0 KB -