oj.uz

Submission #1035010

# Submission time Handle Problem Language Result Execution time Memory
1035010 2024-07-26T02:47:31 Z hotboy2703 Dungeons Game (IOI21_dungeons) C++17
37 / 100
 7000 ms 206928 KB 
#include "dungeons.h"

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define MASK(i) (1LL<<(i))
#define BIT(mask,i) (((mask) >> (i))&1)
const ll MAXN = 4e5+100;
const ll MAXK = 19;
struct path{
	ll x,max1,sum;
};
path sp[MAXK][MAXN];
vector <int> s,p,w,l;
ll n;
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
	n=N;
	s=S,p=P,w=W,l=L;
	for (ll i = 0;i < n;i ++)sp[0][i] = {w[i],s[i],s[i]};
	sp[0][n] = {n,0,0};
	for (ll j = 1;j < MAXK;j ++){
		for (ll i = 0;i <= n;i ++){
			sp[j][i].x = sp[j-1][sp[j-1][i].x].x;
			sp[j][i].max1 = max(sp[j-1][i].max1,sp[j-1][sp[j-1][i].x].max1);
			sp[j][i].sum = sp[j-1][i].sum + sp[j-1][sp[j-1][i].x].sum;
		}
	}
	return;
}

long long simulate(int x, int Z) {
	ll z=Z;
	while (x!=n){
		for (ll j = MAXK-1;j>=0;j--){
			if (sp[j][x].max1 <= z){
				z += sp[j][x].sum;
				x = sp[j][x].x;
			}
		}
		if (x!=n && z < s[x]){
			z+=p[x];
			x=l[x];
		}
	}
	return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 22 ms 29020 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 23 ms 25176 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 203 ms 198484 KB Output is correct
3 Correct 205 ms 205392 KB Output is correct
4 Correct 205 ms 206928 KB Output is correct
5 Correct 214 ms 206928 KB Output is correct
6 Correct 228 ms 205232 KB Output is correct
7 Correct 254 ms 203564 KB Output is correct

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7000 KB Output is correct
2 Correct 37 ms 29788 KB Output is correct
3 Correct 39 ms 29924 KB Output is correct
4 Correct 34 ms 29788 KB Output is correct
5 Correct 32 ms 29788 KB Output is correct
6 Execution timed out 7053 ms 29784 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7000 KB Output is correct
2 Correct 37 ms 29788 KB Output is correct
3 Correct 39 ms 29924 KB Output is correct
4 Correct 34 ms 29788 KB Output is correct
5 Correct 32 ms 29788 KB Output is correct
6 Execution timed out 7053 ms 29784 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7000 KB Output is correct
2 Correct 37 ms 29788 KB Output is correct
3 Correct 39 ms 29924 KB Output is correct
4 Correct 34 ms 29788 KB Output is correct
5 Correct 32 ms 29788 KB Output is correct
6 Execution timed out 7053 ms 29784 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 856 KB Output is correct
2 Correct 203 ms 198484 KB Output is correct
3 Correct 205 ms 205392 KB Output is correct
4 Correct 205 ms 206928 KB Output is correct
5 Correct 214 ms 206928 KB Output is correct
6 Correct 228 ms 205232 KB Output is correct
7 Correct 254 ms 203564 KB Output is correct
8 Correct 2 ms 7000 KB Output is correct
9 Correct 37 ms 29788 KB Output is correct
10 Correct 39 ms 29924 KB Output is correct
11 Correct 34 ms 29788 KB Output is correct
12 Correct 32 ms 29788 KB Output is correct
13 Execution timed out 7053 ms 29784 KB Time limit exceeded
14 Halted 0 ms 0 KB -