oj.uz

Submission #921289

# Submission time Handle Problem Language Result Execution time Memory
921289 2024-02-03T16:21:21 Z byunjaewoo Dungeons Game (IOI21_dungeons) C++17
63 / 100
 4849 ms 2097152 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
 
const int Nmax=400010;
int N, S[Nmax], P[Nmax], W[Nmax], L[Nmax];
ll DP[Nmax];
vector<int> nxt[24][Nmax], mx[24][Nmax], sum[24][Nmax];
 
void init(int n, std::vector<int> S_, std::vector<int> P_, std::vector<int> W_, std::vector<int> L_) {
	N=n;
	for(int i=0; i<N; i++) S[i]=S_[i], P[i]=P_[i], W[i]=W_[i], L[i]=L_[i];
	for(int i=0; i<24; i++) for(int j=0; j<=N; j++) nxt[i][j].resize(i), mx[i][j].resize(i), sum[i][j].resize(i);
	for(int i=1; i<24; i++) {
		for(int j=0; j<N; j++) {
			if(S[j]>=(1<<(i+1))) nxt[i][j][0]=L[j], sum[i][j][0]=P[j], mx[i][j][0]=(1<<(i+1))-1-P[j];
			else if(S[j]<=(1<<i)) nxt[i][j][0]=W[j], sum[i][j][0]=S[j], mx[i][j][0]=(1<<(i+1))-1-S[j];
			else nxt[i][j][0]=L[j], sum[i][j][0]=P[j], mx[i][j][0]=min(S[j]-1, (1<<(i+1))-1-P[j]);
		}
		nxt[i][N][0]=N, sum[i][N][0]=0, mx[i][N][0]=(1<<(i+1))-1;
		for(int j=1; j<i; j++) for(int k=0; k<=N; k++) {
			nxt[i][k][j]=nxt[i][nxt[i][k][j-1]][j-1];
			sum[i][k][j]=sum[i][k][j-1]+sum[i][nxt[i][k][j-1]][j-1];
			if(sum[i][k][j]>2000000000) sum[i][k][j]=2000000000;
			mx[i][k][j]=min(mx[i][k][j-1], mx[i][nxt[i][k][j-1]][j-1]-sum[i][k][j-1]);
		}
	}
	for(int i=N-1; i>=0; i--) DP[i]=DP[W[i]]+S[i];
}
 
long long simulate(int x, int z) {
	int k=x; ll v=z;
	for(int i=0; i<24; i++) {
		int kk=k; ll vv=v;
		for(int j=i-1; j>=0; j--) if(vv<=mx[i][kk][j]) {
			vv+=sum[i][kk][j], kk=nxt[i][kk][j];
			if(kk==N) break;
		}
		if(kk==N) {
			for(int j=i-1; j>=0; j--) if(nxt[i][k][j]!=N) v+=sum[i][k][j], k=nxt[i][k][j];
			if(k!=N) v+=sum[i][k][0], k=nxt[i][k][0];
			return v;
		}
		if(vv<(1<<(i+1))) {
			if(vv>=S[kk]) vv+=S[kk], kk=W[kk];
			else vv+=P[kk], kk=L[kk];
		}
		k=kk, v=vv;
	}
	return v+DP[k];
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 684112 KB Output is correct
2 Correct 168 ms 683856 KB Output is correct
3 Correct 175 ms 692420 KB Output is correct
4 Correct 685 ms 900420 KB Output is correct
5 Correct 180 ms 692484 KB Output is correct
6 Correct 683 ms 899932 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 688212 KB Output is correct
2 Runtime error 1383 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 688208 KB Output is correct
2 Correct 955 ms 900052 KB Output is correct
3 Correct 945 ms 899972 KB Output is correct
4 Correct 978 ms 901112 KB Output is correct
5 Correct 976 ms 901124 KB Output is correct
6 Correct 971 ms 901168 KB Output is correct
7 Correct 1000 ms 901228 KB Output is correct
8 Correct 1497 ms 900976 KB Output is correct
9 Correct 840 ms 901060 KB Output is correct
10 Correct 1330 ms 900948 KB Output is correct
11 Correct 1851 ms 901236 KB Output is correct
12 Correct 4849 ms 901428 KB Output is correct
13 Correct 4489 ms 901200 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 688208 KB Output is correct
2 Correct 955 ms 900052 KB Output is correct
3 Correct 945 ms 899972 KB Output is correct
4 Correct 978 ms 901112 KB Output is correct
5 Correct 976 ms 901124 KB Output is correct
6 Correct 971 ms 901168 KB Output is correct
7 Correct 1000 ms 901228 KB Output is correct
8 Correct 1497 ms 900976 KB Output is correct
9 Correct 840 ms 901060 KB Output is correct
10 Correct 1330 ms 900948 KB Output is correct
11 Correct 1851 ms 901236 KB Output is correct
12 Correct 4849 ms 901428 KB Output is correct
13 Correct 4489 ms 901200 KB Output is correct
14 Correct 174 ms 688092 KB Output is correct
15 Correct 972 ms 901344 KB Output is correct
16 Correct 1002 ms 901436 KB Output is correct
17 Correct 1149 ms 901044 KB Output is correct
18 Correct 1153 ms 901252 KB Output is correct
19 Correct 997 ms 901184 KB Output is correct
20 Correct 1185 ms 901204 KB Output is correct
21 Correct 1347 ms 901108 KB Output is correct
22 Correct 1411 ms 901116 KB Output is correct
23 Correct 2449 ms 901296 KB Output is correct
24 Correct 2476 ms 901064 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 688208 KB Output is correct
2 Correct 955 ms 900052 KB Output is correct
3 Correct 945 ms 899972 KB Output is correct
4 Correct 978 ms 901112 KB Output is correct
5 Correct 976 ms 901124 KB Output is correct
6 Correct 971 ms 901168 KB Output is correct
7 Correct 1000 ms 901228 KB Output is correct
8 Correct 1497 ms 900976 KB Output is correct
9 Correct 840 ms 901060 KB Output is correct
10 Correct 1330 ms 900948 KB Output is correct
11 Correct 1851 ms 901236 KB Output is correct
12 Correct 4849 ms 901428 KB Output is correct
13 Correct 4489 ms 901200 KB Output is correct
14 Correct 174 ms 688092 KB Output is correct
15 Correct 972 ms 901344 KB Output is correct
16 Correct 1002 ms 901436 KB Output is correct
17 Correct 1149 ms 901044 KB Output is correct
18 Correct 1153 ms 901252 KB Output is correct
19 Correct 997 ms 901184 KB Output is correct
20 Correct 1185 ms 901204 KB Output is correct
21 Correct 1347 ms 901108 KB Output is correct
22 Correct 1411 ms 901116 KB Output is correct
23 Correct 2449 ms 901296 KB Output is correct
24 Correct 2476 ms 901064 KB Output is correct
25 Correct 721 ms 900556 KB Output is correct
26 Correct 989 ms 901384 KB Output is correct
27 Correct 939 ms 900948 KB Output is correct
28 Correct 927 ms 901008 KB Output is correct
29 Correct 973 ms 901432 KB Output is correct
30 Correct 1314 ms 901228 KB Output is correct
31 Correct 1414 ms 900848 KB Output is correct
32 Correct 1672 ms 901112 KB Output is correct
33 Correct 944 ms 901140 KB Output is correct
34 Correct 1713 ms 901128 KB Output is correct
35 Correct 1128 ms 901044 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 688212 KB Output is correct
2 Runtime error 1383 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -