oj.uz

답안 #582453

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
582453 2022-06-23T19:33:43 Z PiejanVDC 던전 (IOI21_dungeons) C++17
63 / 100
 4089 ms 1007124 KB 
#include <bits/stdc++.h>
#include "dungeons.h"

using namespace std;

const int mxN = (int)5e4+5;
const int lg = (int)32;

long long lim[mxN][lg][32];
long long gget[mxN][lg][32];
int jump[mxN][lg][32];

int N;
vector<int>S; vector<int>P; vector<int>W; vector<int>L;

void init(int n, vector<int>s, vector<int>p, vector<int>w, vector<int>l) {

    S = s, P = p, W = w, L = l;

	N = n;

	for(int j = 0 ; j < lg ; j++) {
		for(int i = 0 ; i < n ; i++) {
			if(pow(2,j) >= s[i]) {
				lim[i][j][0] = LLONG_MAX;
				gget[i][j][0] = s[i];
				jump[i][j][0] = w[i];
			} else {
				lim[i][j][0] = s[i];
				gget[i][j][0] = p[i];
				jump[i][j][0] = l[i];
			}
		}
	}

	for(int k = 1 ; k < 30 ; k++) {
		for(int j = 0 ; j < lg ; j++) {
			for(int i = 0 ; i < n ; i++) {
				lim[i][j][k] = (lim[i][j][k-1] == LLONG_MAX && lim[ jump[i][j][k-1] ][j][k-1] - gget[i][j][k-1] == LLONG_MAX ? LLONG_MAX : min(lim[i][j][k-1], lim[ jump[i][j][k-1] ][j][k-1] - gget[i][j][k-1]));
				gget[i][j][k] = gget[i][j][k-1] + gget[ jump[i][j][k-1] ][j][k-1];
				jump[i][j][k] = jump[ jump[i][j][k-1] ][j][k-1];
			}
		}
	}

}

long long simulate(int x, int z) {
	long long c = z;
	int pw = 0;

	while(x != N) {
		while(pow(2,(pw+1)) <= c && pw+1 <= 30) {
			pw++;
		}


		for(int j = 30 ; j >= 0 ; j--) {
			if(lim[x][pw][j] > c && jump[x][pw][j] != N) {
				c += gget[x][pw][j];
				x = jump[x][pw][j];
			}
		}
		if(x != N) {
			if(c >= S[x]) {
                c += S[x];
                x = W[x];
			} else {
                c += P[x];
                x = L[x];
			}
		}

	}

	return c;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 92 ms 40472 KB Output is correct
4 Correct 2667 ms 1004612 KB Output is correct
5 Correct 108 ms 40472 KB Output is correct
6 Correct 2730 ms 1004612 KB Output is correct

Subtask #2
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 20412 KB Output is correct
2 Runtime error 970 ms 988796 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 20308 KB Output is correct
2 Correct 3132 ms 1005324 KB Output is correct
3 Correct 2632 ms 1005760 KB Output is correct
4 Correct 2734 ms 1006584 KB Output is correct
5 Correct 2679 ms 1006412 KB Output is correct
6 Correct 2860 ms 1006688 KB Output is correct
7 Correct 3001 ms 1006664 KB Output is correct
8 Correct 2799 ms 1006488 KB Output is correct
9 Correct 2599 ms 1006400 KB Output is correct
10 Correct 2715 ms 1006288 KB Output is correct
11 Correct 3902 ms 1006792 KB Output is correct
12 Correct 4089 ms 1006664 KB Output is correct
13 Correct 2947 ms 1006644 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 20308 KB Output is correct
2 Correct 3132 ms 1005324 KB Output is correct
3 Correct 2632 ms 1005760 KB Output is correct
4 Correct 2734 ms 1006584 KB Output is correct
5 Correct 2679 ms 1006412 KB Output is correct
6 Correct 2860 ms 1006688 KB Output is correct
7 Correct 3001 ms 1006664 KB Output is correct
8 Correct 2799 ms 1006488 KB Output is correct
9 Correct 2599 ms 1006400 KB Output is correct
10 Correct 2715 ms 1006288 KB Output is correct
11 Correct 3902 ms 1006792 KB Output is correct
12 Correct 4089 ms 1006664 KB Output is correct
13 Correct 2947 ms 1006644 KB Output is correct
14 Correct 50 ms 20436 KB Output is correct
15 Correct 2809 ms 1006792 KB Output is correct
16 Correct 3292 ms 1007124 KB Output is correct
17 Correct 2695 ms 1006516 KB Output is correct
18 Correct 2791 ms 1006540 KB Output is correct
19 Correct 2941 ms 1006660 KB Output is correct
20 Correct 2813 ms 1006404 KB Output is correct
21 Correct 2777 ms 1006532 KB Output is correct
22 Correct 2858 ms 1006536 KB Output is correct
23 Correct 3796 ms 1006760 KB Output is correct
24 Correct 3979 ms 1006660 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 20308 KB Output is correct
2 Correct 3132 ms 1005324 KB Output is correct
3 Correct 2632 ms 1005760 KB Output is correct
4 Correct 2734 ms 1006584 KB Output is correct
5 Correct 2679 ms 1006412 KB Output is correct
6 Correct 2860 ms 1006688 KB Output is correct
7 Correct 3001 ms 1006664 KB Output is correct
8 Correct 2799 ms 1006488 KB Output is correct
9 Correct 2599 ms 1006400 KB Output is correct
10 Correct 2715 ms 1006288 KB Output is correct
11 Correct 3902 ms 1006792 KB Output is correct
12 Correct 4089 ms 1006664 KB Output is correct
13 Correct 2947 ms 1006644 KB Output is correct
14 Correct 50 ms 20436 KB Output is correct
15 Correct 2809 ms 1006792 KB Output is correct
16 Correct 3292 ms 1007124 KB Output is correct
17 Correct 2695 ms 1006516 KB Output is correct
18 Correct 2791 ms 1006540 KB Output is correct
19 Correct 2941 ms 1006660 KB Output is correct
20 Correct 2813 ms 1006404 KB Output is correct
21 Correct 2777 ms 1006532 KB Output is correct
22 Correct 2858 ms 1006536 KB Output is correct
23 Correct 3796 ms 1006760 KB Output is correct
24 Correct 3979 ms 1006660 KB Output is correct
25 Correct 2991 ms 1005984 KB Output is correct
26 Correct 3115 ms 1007012 KB Output is correct
27 Correct 2729 ms 1006456 KB Output is correct
28 Correct 2619 ms 1006524 KB Output is correct
29 Correct 3034 ms 1006920 KB Output is correct
30 Correct 3011 ms 1006664 KB Output is correct
31 Correct 2995 ms 1006512 KB Output is correct
32 Correct 3967 ms 1006536 KB Output is correct
33 Correct 3237 ms 1006264 KB Output is correct
34 Correct 3838 ms 1006112 KB Output is correct
35 Correct 3539 ms 1006552 KB Output is correct

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 20412 KB Output is correct
2 Runtime error 970 ms 988796 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -