oj.uz

Submission #1012242

# Submission time Handle Problem Language Result Execution time Memory
1012242 2024-07-01T21:05:41 Z 1ne Dungeons Game (IOI21_dungeons) C++17
26 / 100
 798 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) {
	unordered_map<int,long long>mp;
	long long Z = z;
	int cnt = 0;
	auto check = [&](int xx){
		if (xx != N && mp.find(xx) != mp.end() && S[xx] > Z && Z != mp[xx]){
			long long v = Z - mp[xx];
			long long k = (S[xx] - Z + v - 1) / v;
			Z+=k * v;			
		}
		mp[xx] = Z;
	};
	while(x != N){
		check(x);
		cnt++;
		//assert(cnt < 50);
	//	cout<<x<<"->";
		long long c = -1;
		int left = 0,right = k - 1;
		while(left <= right){
			int mid = (left + right)>>1;
			if (nx[x][mid] != -1 && table[x][mid] <= Z){
				left = mid + 1;
				c = mid;
			}
			else right = mid - 1;
		}
		++c;
		//while(nx[x][c] != -1 && table[x][c] <= Z){
		//	++c;
		//}
		if (c != 0){
			Z+=sum[x][c - 1];
			x = nx[x][c - 1];	
		}
		check(x);
		if (x != N && S[x] > Z){
			int cc = 0;
			while(bk[x][cc]!=-1 && need[x][cc] > Z){
				++cc;
			}
			cc--;
			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];
						check(x);
					}
				}
				else cc--;
			}
			//cout<<'\n';
		}	
	}
//	cout<<'\n';
	return Z;
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1624 KB Output is correct
2 Correct 737 ms 489528 KB Output is correct
3 Correct 780 ms 489556 KB Output is correct
4 Correct 720 ms 489544 KB Output is correct
5 Correct 595 ms 489680 KB Output is correct
6 Correct 798 ms 489812 KB Output is correct
7 Correct 696 ms 489556 KB Output is correct

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1628 KB Output is correct
2 Correct 91 ms 62168 KB Output is correct
3 Correct 133 ms 62140 KB Output is correct
4 Correct 112 ms 62036 KB Output is correct
5 Correct 120 ms 62276 KB Output is correct
6 Incorrect 113 ms 62040 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1628 KB Output is correct
2 Correct 91 ms 62168 KB Output is correct
3 Correct 133 ms 62140 KB Output is correct
4 Correct 112 ms 62036 KB Output is correct
5 Correct 120 ms 62276 KB Output is correct
6 Incorrect 113 ms 62040 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1628 KB Output is correct
2 Correct 91 ms 62168 KB Output is correct
3 Correct 133 ms 62140 KB Output is correct
4 Correct 112 ms 62036 KB Output is correct
5 Correct 120 ms 62276 KB Output is correct
6 Incorrect 113 ms 62040 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1624 KB Output is correct
2 Correct 737 ms 489528 KB Output is correct
3 Correct 780 ms 489556 KB Output is correct
4 Correct 720 ms 489544 KB Output is correct
5 Correct 595 ms 489680 KB Output is correct
6 Correct 798 ms 489812 KB Output is correct
7 Correct 696 ms 489556 KB Output is correct
8 Correct 2 ms 1628 KB Output is correct
9 Correct 91 ms 62168 KB Output is correct
10 Correct 133 ms 62140 KB Output is correct
11 Correct 112 ms 62036 KB Output is correct
12 Correct 120 ms 62276 KB Output is correct
13 Incorrect 113 ms 62040 KB Output isn't correct
14 Halted 0 ms 0 KB -