oj.uz

Submission #439896

# Submission time Handle Problem Language Result Execution time Memory
439896 2021-07-01T06:35:05 Z cheeheng Dungeons Game (IOI21_dungeons) C++17
25 / 100
 549 ms 93164 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

int S[400005];
int P[400005];
int W[400005];
int L[400005];

int N;

vector<long long> cutoff;
int parent[400005][25][6];
long long cost[400005][25][6];
const long long INF = 1LL << 62;

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
    N = n;
    cutoff.push_back(0);
    cutoff.push_back(INF);
    for(int i = 0; i < N; i ++){
        S[i] = s[i];
        P[i] = p[i];
        W[i] = w[i];
        L[i] = l[i];
        cutoff.push_back(S[i]);
    }

    sort(cutoff.begin(), cutoff.end());
    cutoff.erase(unique(cutoff.begin(), cutoff.end()), cutoff.end());

    assert((int)cutoff.size() <= 7);

    while((int)cutoff.size() < 7){
        cutoff.push_back(INF);
    }

    for(int j = 0; j < 6; j ++){
        for(int i = 0; i < N; i ++){
            parent[i][0][j] = (cutoff[j] >= S[i]) ? W[i] : L[i];
            cost[i][0][j] = (cutoff[j] >= S[i]) ? S[i] : P[i];
        }
        parent[N][0][j] = -1;
    }

    for(int j = 0; j < 6; j ++){
        for(int k = 1; k < 25; k ++){
            for(int i = 0; i <= N; i ++){
                if(parent[i][k-1][j] == -1){
                    parent[i][k][j] = -1;
                }else{
                    parent[i][k][j] = parent[parent[i][k-1][j]][k-1][j];
                    cost[i][k][j] = cost[i][k-1][j] + cost[parent[i][k-1][j]][k-1][j];
                }
            }
        }
    }

	return;
}

long long op = 0;
long long simulate(int x, int z) {
    long long ans = z;
    int cur = x;

    for(int j = 0; j < 6; j ++){
        for(int k = 24; k >= 0; k --){
            if(parent[cur][k][j] != -1){
                long long tempCost = cost[cur][k][j];
                if(ans + tempCost < cutoff[j+1]){
                    ans += tempCost;
                    cur = parent[cur][k][j];
                }
            }
        }

        if(ans < cutoff[j+1]){
            if(parent[cur][0][j] != -1){
                ans += cost[cur][0][j];
                cur = parent[cur][0][j];
            }
        }
        //printf("ans=%lld; cutoff=%lld\n", ans, cutoff[j]);
    }

    assert(cur == N);
	return ans;
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Runtime error 32 ms 332 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2144 KB Output is correct
2 Correct 323 ms 92472 KB Output is correct
3 Correct 394 ms 92364 KB Output is correct
4 Correct 376 ms 92560 KB Output is correct
5 Correct 375 ms 92480 KB Output is correct
6 Correct 289 ms 92512 KB Output is correct
7 Correct 271 ms 93068 KB Output is correct
8 Correct 408 ms 92860 KB Output is correct
9 Correct 313 ms 92872 KB Output is correct
10 Correct 353 ms 92860 KB Output is correct
11 Correct 350 ms 92988 KB Output is correct
12 Correct 549 ms 93080 KB Output is correct
13 Correct 370 ms 93076 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2144 KB Output is correct
2 Correct 323 ms 92472 KB Output is correct
3 Correct 394 ms 92364 KB Output is correct
4 Correct 376 ms 92560 KB Output is correct
5 Correct 375 ms 92480 KB Output is correct
6 Correct 289 ms 92512 KB Output is correct
7 Correct 271 ms 93068 KB Output is correct
8 Correct 408 ms 92860 KB Output is correct
9 Correct 313 ms 92872 KB Output is correct
10 Correct 353 ms 92860 KB Output is correct
11 Correct 350 ms 92988 KB Output is correct
12 Correct 549 ms 93080 KB Output is correct
13 Correct 370 ms 93076 KB Output is correct
14 Correct 4 ms 2124 KB Output is correct
15 Correct 322 ms 92968 KB Output is correct
16 Correct 396 ms 93080 KB Output is correct
17 Correct 484 ms 92936 KB Output is correct
18 Correct 514 ms 92944 KB Output is correct
19 Correct 389 ms 93088 KB Output is correct
20 Correct 455 ms 92940 KB Output is correct
21 Correct 522 ms 92996 KB Output is correct
22 Correct 338 ms 92988 KB Output is correct
23 Correct 487 ms 93164 KB Output is correct
24 Correct 524 ms 92988 KB Output is correct

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2144 KB Output is correct
2 Correct 323 ms 92472 KB Output is correct
3 Correct 394 ms 92364 KB Output is correct
4 Correct 376 ms 92560 KB Output is correct
5 Correct 375 ms 92480 KB Output is correct
6 Correct 289 ms 92512 KB Output is correct
7 Correct 271 ms 93068 KB Output is correct
8 Correct 408 ms 92860 KB Output is correct
9 Correct 313 ms 92872 KB Output is correct
10 Correct 353 ms 92860 KB Output is correct
11 Correct 350 ms 92988 KB Output is correct
12 Correct 549 ms 93080 KB Output is correct
13 Correct 370 ms 93076 KB Output is correct
14 Correct 4 ms 2124 KB Output is correct
15 Correct 322 ms 92968 KB Output is correct
16 Correct 396 ms 93080 KB Output is correct
17 Correct 484 ms 92936 KB Output is correct
18 Correct 514 ms 92944 KB Output is correct
19 Correct 389 ms 93088 KB Output is correct
20 Correct 455 ms 92940 KB Output is correct
21 Correct 522 ms 92996 KB Output is correct
22 Correct 338 ms 92988 KB Output is correct
23 Correct 487 ms 93164 KB Output is correct
24 Correct 524 ms 92988 KB Output is correct
25 Runtime error 62 ms 4248 KB Execution killed with signal 6
26 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 460 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -