oj.uz

Submission #437127

# Submission time Handle Problem Language Result Execution time Memory
437127 2021-06-25T21:54:24 Z jeroenodb Dungeons Game (IOI21_dungeons) C++17
37 / 100
 7000 ms 122644 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;
const int LOG = 20;
int jmp[mxN][LOG], fastjmp[mxN];
ll fastsm[mxN];
bitset<mxN> mx[LOG];
ll sm[mxN][LOG];
static int N;
const int B = 4000;
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<LOG;++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 j=0;j<n;++j) {
		int x=j;
		for(int i=LOG-1;i>=0;--i) {
			if(!mx[i][x]) {
				fastsm[j]+=sm[x][i];
				x=jmp[x][i];
			}
		}
		fastjmp[j]=x;
	}
	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) {
		z+=fastsm[x];
		x=fastjmp[x];
		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 56 ms 15556 KB Output is correct
5 Correct 2 ms 972 KB Output is correct
6 Correct 55 ms 15560 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 543 ms 122552 KB Output is correct
3 Correct 484 ms 122596 KB Output is correct
4 Correct 481 ms 122516 KB Output is correct
5 Correct 494 ms 122560 KB Output is correct
6 Correct 658 ms 122644 KB Output is correct
7 Correct 686 ms 122564 KB Output is correct

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 77 ms 15944 KB Output is correct
3 Correct 95 ms 15920 KB Output is correct
4 Correct 95 ms 16324 KB Output is correct
5 Correct 74 ms 16372 KB Output is correct
6 Execution timed out 7005 ms 15964 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 716 KB Output is correct
2 Correct 77 ms 15944 KB Output is correct
3 Correct 95 ms 15920 KB Output is correct
4 Correct 95 ms 16324 KB Output is correct
5 Correct 74 ms 16372 KB Output is correct
6 Execution timed out 7005 ms 15964 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 716 KB Output is correct
2 Correct 77 ms 15944 KB Output is correct
3 Correct 95 ms 15920 KB Output is correct
4 Correct 95 ms 16324 KB Output is correct
5 Correct 74 ms 16372 KB Output is correct
6 Execution timed out 7005 ms 15964 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 543 ms 122552 KB Output is correct
3 Correct 484 ms 122596 KB Output is correct
4 Correct 481 ms 122516 KB Output is correct
5 Correct 494 ms 122560 KB Output is correct
6 Correct 658 ms 122644 KB Output is correct
7 Correct 686 ms 122564 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 77 ms 15944 KB Output is correct
10 Correct 95 ms 15920 KB Output is correct
11 Correct 95 ms 16324 KB Output is correct
12 Correct 74 ms 16372 KB Output is correct
13 Execution timed out 7005 ms 15964 KB Time limit exceeded
14 Halted 0 ms 0 KB -