oj.uz

Submission #437126

# Submission time Handle Problem Language Result Execution time Memory
437126 2021-06-25T21:48:25 Z jeroenodb Dungeons Game (IOI21_dungeons) C++17
37 / 100
 7000 ms 117940 KB 
#ifndef GRADER
#include "dungeons.h"
#endif
#pragma GCC optimize "Ofast"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 4e5+10, oo = 1e8;

int jmp[mxN][20];
bitset<mxN> mx[20];
ll sm[mxN][20];
static int N;
const int B = 11000;
vi S,P,W,L;
ll prefsum[mxN] = {};
void init(int n, vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
	S=s,P=p,W=w,L=l;
	N=n;
	jmp[n][0]=n;
	mx[0][n]=true;
	for(int j=0;j<n;++j) {
		if(s[j]>=B) {
			jmp[j][0] = l[j], sm[j][0]=p[j];
		} else jmp[j][0] = w[j], sm[j][0] = s[j];
		mx[0][j] = s[j]>=B;
	}

	for(int i=1;i<20;++i) {
		for(int j=0;j<=n;++j) {
			jmp[j][i] = jmp[jmp[j][i-1]][i-1];
			mx[i][j] = mx[i-1][j] or mx[i-1][jmp[j][i-1]];
			sm[j][i] = sm[j][i-1]+sm[jmp[j][i-1]][i-1];
		}
	}
	for(int i=n-1;i>=0;--i) {
		prefsum[i]=S[i]+prefsum[W[i]];
	}
}

long long mysimulate(int x, ll z) {
	int n = N;
	while(z<B) {
		if(x==n) return z;
		if(z>=S[x]) {
			z+=S[x];
			x=W[x];
		} else {
			z+=P[x];
			x=L[x];
		}
	}
	// find next x: S[x]>z, can only happen log times
	// what if P[x] is very small?

	while(x!=n and z<=1e7) {
		for(int i=19;i>=0;--i) {
			if(!mx[i][x]) {
				z+=sm[x][i];
				x=jmp[x][i];
			}
		}
		if(x==n) return z;
		if(z>=S[x]) {
			z+=S[x];
			x=W[x];
		} else {
			z+=P[x];
			x=L[x];
		}
	}
	return prefsum[x]+z;
}
long long simulate(int x, int z) {
	return mysimulate(x,z);	
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 972 KB Output is correct
4 Correct 48 ms 14920 KB Output is correct
5 Correct 2 ms 972 KB Output is correct
6 Correct 46 ms 14944 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 460 ms 117828 KB Output is correct
3 Correct 438 ms 117828 KB Output is correct
4 Correct 473 ms 117940 KB Output is correct
5 Correct 492 ms 117904 KB Output is correct
6 Correct 759 ms 117880 KB Output is correct
7 Correct 1026 ms 117828 KB Output is correct

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 79 ms 15732 KB Output is correct
3 Correct 77 ms 15704 KB Output is correct
4 Correct 77 ms 15772 KB Output is correct
5 Correct 76 ms 15704 KB Output is correct
6 Execution timed out 7003 ms 15696 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 588 KB Output is correct
2 Correct 79 ms 15732 KB Output is correct
3 Correct 77 ms 15704 KB Output is correct
4 Correct 77 ms 15772 KB Output is correct
5 Correct 76 ms 15704 KB Output is correct
6 Execution timed out 7003 ms 15696 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 588 KB Output is correct
2 Correct 79 ms 15732 KB Output is correct
3 Correct 77 ms 15704 KB Output is correct
4 Correct 77 ms 15772 KB Output is correct
5 Correct 76 ms 15704 KB Output is correct
6 Execution timed out 7003 ms 15696 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 460 ms 117828 KB Output is correct
3 Correct 438 ms 117828 KB Output is correct
4 Correct 473 ms 117940 KB Output is correct
5 Correct 492 ms 117904 KB Output is correct
6 Correct 759 ms 117880 KB Output is correct
7 Correct 1026 ms 117828 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 79 ms 15732 KB Output is correct
10 Correct 77 ms 15704 KB Output is correct
11 Correct 77 ms 15772 KB Output is correct
12 Correct 76 ms 15704 KB Output is correct
13 Execution timed out 7003 ms 15696 KB Time limit exceeded
14 Halted 0 ms 0 KB -