oj.uz

Submission #1011111

# Submission time Handle Problem Language Result Execution time Memory
1011111 2024-06-29T20:08:44 Z 1ne Dungeons Game (IOI21_dungeons) C++17
0 / 100
 7000 ms 860 KB 
#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int k = 20;
vector<vector<long long>>table;
vector<vector<long long>>nx;
vector<vector<long long>>sum;
vector<int>S,P,W,L;
long long N;	
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
	table.resize(n,vector<long long>(k));
	nx.resize(n,vector<long long>(k,-1));
	sum.resize(n,vector<long long>(k,0));
	N = n;
	S = s;
	P = p;
	W = w;
	L = l;
	for (long long i = 0;i<n;++i){
		table[i][0] = s[i];
		nx[i][0] = w[i];
		sum[i][0] = s[i];
	}
	for (long long i = 1;i<k;++i){
			for (long long j = 0;j<n;++j){
			if (nx[j][i - 1] == -1 || nx[j][i - 1] == n)continue;
			//cout<<nx[j][i - 1]<<'\n';
			nx[j][i] = nx[nx[j][i - 1]][i - 1];
			table[j][i] = max(table[j][i - 1],table[nx[j][i - 1]][i - 1] - sum[j][i - 1]);
			sum[j][i] = sum[j][i - 1] + sum[nx[j][i - 1]][i - 1];
		}
	}
	return;
}
 
long long simulate(int x, int z) {
	long long Z = z;
	while(x != N){
	//	cout<<x<<"->";
		long long c = 0;
		while(nx[x][c] != -1 && table[x][c] <= Z){
			++c;
		}
		if (c != 0){
			Z+=sum[x][c - 1];
			x = nx[x][c - 1];
		}
		if (x != N){
			Z+=P[x];
			x = L[x];
		}	
	}
//	cout<<'\n';
	return Z;
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Execution timed out 7085 ms 348 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7068 ms 860 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7059 ms 860 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7059 ms 860 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7059 ms 860 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 7068 ms 860 KB Time limit exceeded
2 Halted 0 ms 0 KB -