oj.uz

Submission #437129

# Submission time Handle Problem Language Result Execution time Memory
437129 2021-06-25T21:56:46 Z jeroenodb Dungeons Game (IOI21_dungeons) C++17
37 / 100
 7000 ms 122616 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;
		assert(S[x]>=B);
		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 52 ms 15560 KB Output is correct
5 Correct 2 ms 972 KB Output is correct
6 Correct 55 ms 15572 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 542 ms 122572 KB Output is correct
3 Correct 479 ms 122616 KB Output is correct
4 Correct 523 ms 122552 KB Output is correct
5 Correct 504 ms 122568 KB Output is correct
6 Correct 684 ms 122560 KB Output is correct
7 Correct 725 ms 122544 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 80 ms 15948 KB Output is correct
3 Correct 91 ms 15940 KB Output is correct
4 Correct 71 ms 16348 KB Output is correct
5 Correct 71 ms 16280 KB Output is correct
6 Execution timed out 7007 ms 16068 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 80 ms 15948 KB Output is correct
3 Correct 91 ms 15940 KB Output is correct
4 Correct 71 ms 16348 KB Output is correct
5 Correct 71 ms 16280 KB Output is correct
6 Execution timed out 7007 ms 16068 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 80 ms 15948 KB Output is correct
3 Correct 91 ms 15940 KB Output is correct
4 Correct 71 ms 16348 KB Output is correct
5 Correct 71 ms 16280 KB Output is correct
6 Execution timed out 7007 ms 16068 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 542 ms 122572 KB Output is correct
3 Correct 479 ms 122616 KB Output is correct
4 Correct 523 ms 122552 KB Output is correct
5 Correct 504 ms 122568 KB Output is correct
6 Correct 684 ms 122560 KB Output is correct
7 Correct 725 ms 122544 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 80 ms 15948 KB Output is correct
10 Correct 91 ms 15940 KB Output is correct
11 Correct 71 ms 16348 KB Output is correct
12 Correct 71 ms 16280 KB Output is correct
13 Execution timed out 7007 ms 16068 KB Time limit exceeded
14 Halted 0 ms 0 KB -