oj.uz

Submission #1049113

# Submission time Handle Problem Language Result Execution time Memory
1049113 2024-08-08T13:28:26 Z parsadox2 Dungeons Game (IOI21_dungeons) C++17
0 / 100
 1607 ms 402076 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;

const int N = 4e5 + 10 , Lg = 20;
const long long inf = 1e15 + 10;

int n;

vector <int> s , p , w , l;

long long f(long long x)
{
	if(x <= 0)
		return inf;
	return x;
}

struct item{
	long long mn;
	long long val;
	int id;
};

item a[2 * N][Lg];

item Get(item now , int len)
{
	while(len != 0)
	{
		long long id = now.id , mn = now.mn , val = now.val , dif = val - (val >= s[id]) * s[id];

		for(int i = Lg - 1 ; i >= 0 ; i--)  if((1 << i) <= len && a[id * 2 + (val >= s[id])][i].mn > dif)
		{
			item tmp = a[id * 2 + (val >= s[id])][i];
			now = {min(mn , tmp.mn - dif) , tmp.val + dif , tmp.id};
			len = len - (1 << i);
			break;
		}
		if(len == 0)
			break;
		if(val >= s[id])
		{
			now = {min(mn , f(s[w[id]] - val - s[id])) , val + s[id] , w[id]};
			len--;
		}
		else
		{
			now = {min(mn , f(s[l[id]] - val - p[id])) , val + p[id] , l[id]};
			len--;
		}
	}
	return now;
}

void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll) {
	n = nn;
	s = ss;
	p = pp;
	w = ww;
	l = ll;
	s.push_back(0);
	p.push_back(0);
	w.push_back(n);
	l.push_back(n);
	for(int i = 0 ; i <= n ; i++)
	{
		a[i << 1][0] = {f(s[l[i]] - p[i]) , p[i] , l[i]};
		a[(i << 1) + 1][0] = {f(s[w[i]] - 2 * s[i]) , 2 * s[i] , w[i]};
	}
	for(int j = 1 ; j < Lg ; j++)  for(int i = 0 ; i <= 2 * n + 1 ; i++)
	{
		a[i][j] = Get(a[i][j - 1] , (1 << (j - 1)));
	}
}

long long simulate(int x, int z) {
	item tmp = Get({inf , z , x} , 2e7);
	return tmp.val;
}

Subtask #1
0.0 / 11.0

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

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2792 KB Output is correct
2 Incorrect 1607 ms 402076 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 77 ms 51968 KB Output is correct
3 Incorrect 92 ms 51572 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 77 ms 51968 KB Output is correct
3 Incorrect 92 ms 51572 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 77 ms 51968 KB Output is correct
3 Incorrect 92 ms 51572 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2792 KB Output is correct
2 Incorrect 1607 ms 402076 KB Output isn't correct
3 Halted 0 ms 0 KB -