oj.uz

답안 #437125

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
437125 2021-06-25T21:46:29 Z jeroenodb 던전 (IOI21_dungeons) C++17
37 / 100
 7000 ms 117920 KB 
#ifndef GRADER
#include "dungeons.h"
#endif
#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 = 7000;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 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 59 ms 14920 KB Output is correct
5 Correct 2 ms 972 KB Output is correct
6 Correct 51 ms 14928 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 520 ms 117856 KB Output is correct
3 Correct 504 ms 117816 KB Output is correct
4 Correct 451 ms 117820 KB Output is correct
5 Correct 483 ms 117920 KB Output is correct
6 Correct 670 ms 117904 KB Output is correct
7 Correct 920 ms 117828 KB Output is correct

Subtask #3
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 76 ms 15684 KB Output is correct
3 Correct 77 ms 15836 KB Output is correct
4 Correct 89 ms 15684 KB Output is correct
5 Correct 91 ms 15708 KB Output is correct
6 Execution timed out 7053 ms 15708 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 76 ms 15684 KB Output is correct
3 Correct 77 ms 15836 KB Output is correct
4 Correct 89 ms 15684 KB Output is correct
5 Correct 91 ms 15708 KB Output is correct
6 Execution timed out 7053 ms 15708 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 76 ms 15684 KB Output is correct
3 Correct 77 ms 15836 KB Output is correct
4 Correct 89 ms 15684 KB Output is correct
5 Correct 91 ms 15708 KB Output is correct
6 Execution timed out 7053 ms 15708 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 716 KB Output is correct
2 Correct 520 ms 117856 KB Output is correct
3 Correct 504 ms 117816 KB Output is correct
4 Correct 451 ms 117820 KB Output is correct
5 Correct 483 ms 117920 KB Output is correct
6 Correct 670 ms 117904 KB Output is correct
7 Correct 920 ms 117828 KB Output is correct
8 Correct 2 ms 716 KB Output is correct
9 Correct 76 ms 15684 KB Output is correct
10 Correct 77 ms 15836 KB Output is correct
11 Correct 89 ms 15684 KB Output is correct
12 Correct 91 ms 15708 KB Output is correct
13 Execution timed out 7053 ms 15708 KB Time limit exceeded
14 Halted 0 ms 0 KB -