oj.uz

Submission #1011119

# Submission time Handle Problem Language Result Execution time Memory
1011119 2024-06-29T20:35:45 Z 1ne Dungeons Game (IOI21_dungeons) C++17
50 / 100
 764 ms 489812 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>>bk;
vector<vector<long long>>sum;
vector<vector<long long>>bksum;
vector<vector<long long>>need;
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));
	need.resize(n,vector<long long>(k,1e16));
	bk.resize(n,vector<long long>(k,-1));
	bksum.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];
		need[i][0] = s[i];
		bk[i][0] = l[i];
		bksum[i][0] = p[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];
		}
	}
	for (long long i = 1;i<k;++i){
			for (long long j = 0;j<n;++j){
			if (bk[j][i - 1] == -1 || bk[j][i - 1] == n)continue;
			//cout<<nx[j][i - 1]<<'\n';
			bk[j][i] = bk[bk[j][i - 1]][i - 1];
			need[j][i] = min(need[j][i - 1],need[bk[j][i - 1]][i - 1] - bksum[j][i - 1]);
			bksum[j][i] = bksum[j][i - 1] + bksum[bk[j][i - 1]][i - 1];
		}
	}
	return;
}
 
long long simulate(int x, int z) {
	long long Z = z;
	int cnt = 0;
	while(x != N){
		cnt++;
		assert(cnt < 50);
	//	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 && S[x] > Z){
			int cc = k - 1;
			while(cc >= 0 && x != N){
			//	cout<<x<<"->";
				if (bk[x][cc] != -1){
					if (need[x][cc] <= Z){
						cc--;
					}	 
					else{
						Z+=bksum[x][cc];
						x = bk[x][cc];
					}
				}
				else cc--;
			}
			//cout<<'\n';
		}	
	}
//	cout<<'\n';
	return Z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 3 ms 2652 KB Output is correct
4 Correct 64 ms 61264 KB Output is correct
5 Correct 2 ms 2648 KB Output is correct
6 Correct 66 ms 61564 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1628 KB Output is correct
2 Correct 713 ms 489524 KB Output is correct
3 Correct 711 ms 489780 KB Output is correct
4 Correct 701 ms 489812 KB Output is correct
5 Correct 603 ms 489560 KB Output is correct
6 Correct 764 ms 489560 KB Output is correct
7 Correct 655 ms 489540 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1624 KB Output is correct
2 Correct 90 ms 62036 KB Output is correct
3 Correct 106 ms 62036 KB Output is correct
4 Correct 85 ms 62044 KB Output is correct
5 Correct 94 ms 62272 KB Output is correct
6 Correct 97 ms 62268 KB Output is correct
7 Correct 97 ms 63312 KB Output is correct
8 Correct 96 ms 63044 KB Output is correct
9 Correct 104 ms 63316 KB Output is correct
10 Correct 94 ms 63044 KB Output is correct
11 Correct 100 ms 63316 KB Output is correct
12 Correct 198 ms 63564 KB Output is correct
13 Correct 172 ms 63312 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1624 KB Output is correct
2 Correct 90 ms 62036 KB Output is correct
3 Correct 106 ms 62036 KB Output is correct
4 Correct 85 ms 62044 KB Output is correct
5 Correct 94 ms 62272 KB Output is correct
6 Correct 97 ms 62268 KB Output is correct
7 Correct 97 ms 63312 KB Output is correct
8 Correct 96 ms 63044 KB Output is correct
9 Correct 104 ms 63316 KB Output is correct
10 Correct 94 ms 63044 KB Output is correct
11 Correct 100 ms 63316 KB Output is correct
12 Correct 198 ms 63564 KB Output is correct
13 Correct 172 ms 63312 KB Output is correct
14 Correct 2 ms 1628 KB Output is correct
15 Runtime error 105 ms 125600 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1624 KB Output is correct
2 Correct 90 ms 62036 KB Output is correct
3 Correct 106 ms 62036 KB Output is correct
4 Correct 85 ms 62044 KB Output is correct
5 Correct 94 ms 62272 KB Output is correct
6 Correct 97 ms 62268 KB Output is correct
7 Correct 97 ms 63312 KB Output is correct
8 Correct 96 ms 63044 KB Output is correct
9 Correct 104 ms 63316 KB Output is correct
10 Correct 94 ms 63044 KB Output is correct
11 Correct 100 ms 63316 KB Output is correct
12 Correct 198 ms 63564 KB Output is correct
13 Correct 172 ms 63312 KB Output is correct
14 Correct 2 ms 1628 KB Output is correct
15 Runtime error 105 ms 125600 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1628 KB Output is correct
2 Correct 713 ms 489524 KB Output is correct
3 Correct 711 ms 489780 KB Output is correct
4 Correct 701 ms 489812 KB Output is correct
5 Correct 603 ms 489560 KB Output is correct
6 Correct 764 ms 489560 KB Output is correct
7 Correct 655 ms 489540 KB Output is correct
8 Correct 2 ms 1624 KB Output is correct
9 Correct 90 ms 62036 KB Output is correct
10 Correct 106 ms 62036 KB Output is correct
11 Correct 85 ms 62044 KB Output is correct
12 Correct 94 ms 62272 KB Output is correct
13 Correct 97 ms 62268 KB Output is correct
14 Correct 97 ms 63312 KB Output is correct
15 Correct 96 ms 63044 KB Output is correct
16 Correct 104 ms 63316 KB Output is correct
17 Correct 94 ms 63044 KB Output is correct
18 Correct 100 ms 63316 KB Output is correct
19 Correct 198 ms 63564 KB Output is correct
20 Correct 172 ms 63312 KB Output is correct
21 Correct 2 ms 1628 KB Output is correct
22 Runtime error 105 ms 125600 KB Execution killed with signal 6
23 Halted 0 ms 0 KB -