oj.uz

Submission #1049945

# Submission time Handle Problem Language Result Execution time Memory
1049945 2024-08-09T06:16:41 Z Alihan_8 Dungeons Game (IOI21_dungeons) C++17
63 / 100
 3087 ms 2097152 KB 
#include "dungeons.h"
#include <vector>

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

const i64 inf = 1e15;

const int L = 24;

const int B = 20;

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

int n;

struct Jump{
	vector <vector<int>> U;
	vector <vector<i64>> S, need;
	
	int n, lim;
	
	Jump() {}
	
	void modify(vector <int> p, vector <int> w, int lim_){
		n = p.size(); lim = lim_;
		
		S.resize(n + 1); 
		U.resize(n + 1);
		need.resize(n + 1);
		
		for ( int i = 0; i <= n; i++ ){
			S[i].resize(L);
			U[i].resize(L);
			need[i].resize(L);
			
			if ( i == n ) continue;
			
			S[i][0] = w[i];
			U[i][0] = p[i];
			need[i][0] = (s[i] >= lim ? s[i] : inf);
		}
	
		U[n][0] = n;
		S[n][0] = inf;
		
		for ( int i = 1; i < L; i++ ){
			for ( int j = 0; j <= n; j++ ){
				U[j][i] = U[U[j][i - 1]][i - 1];
				S[j][i] = min(inf, S[j][i - 1] + S[U[j][i - 1]][i - 1]);
				need[j][i] = min(need[j][i - 1], need[U[j][i - 1]][i - 1] - S[j][i - 1]);
			}
		}
	}
	
	i64 simulate(int &u, i64 z, i64 rq){
		for ( int i = L - 1; i >= 0; i-- ){
			if ( U[u][i] == n ) continue;
			
			if ( rq == inf || (need[u][i] > z && z + S[u][i] < rq) ){
				z += S[u][i];
				u = U[u][i];
			}
		}
		
		if ( u != n && z < rq ){
			if ( s[u] <= z ){
				z += s[u];
				u = w[u];
			} else{
				z += p[u];
				u = l[u];
			}
		}
		
		return z;
	};
};

vector <Jump> A;

vector <i64> v;

void init(int n_, std::vector<int> s_, std::vector<int> p_, std::vector<int> w_, std::vector<int> l_) {
	n = n_, s = s_, p = p_, w = w_, l = l_;
	
	//~ for ( auto &u: s ) v.pb(u);
	
	v.pb(inf); v.pb(1);
	
	while ( v.back() <= 1e7 ){
		v.pb(v.back() * B);
	}
	
	sort(all(v));
	
	v.resize(unique(all(v)) - v.begin());
	
	for ( auto &x: v ){
		vector <int> fa(n), wh(n);
		
		for ( int i = 0; i < n; i++ ){
			if ( s[i] < x ){
				fa[i] = w[i];
				wh[i] = s[i];
			} else{
				fa[i] = l[i];
				wh[i] = p[i];
			}
		}
		
		Jump h; h.modify(fa, wh, x);
		
		A.pb(h);
	}
}

long long simulate(int x, int Z) {
	// subtask #4
	
	i64 z = Z;
	
	for ( int i = 0; i + 2 < (int)v.size(); i++ ){
		while ( (z = A[i].simulate(x, z, v[i + 1])) < v[i + 1] && x != n ){
			continue;
		}
	}
	
	z = A.back().simulate(x, z, inf);
	
	return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 10 ms 10932 KB Output is correct
4 Correct 303 ms 268160 KB Output is correct
5 Correct 9 ms 11100 KB Output is correct
6 Correct 305 ms 268284 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5720 KB Output is correct
2 Runtime error 3087 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5720 KB Output is correct
2 Correct 404 ms 269188 KB Output is correct
3 Correct 464 ms 269468 KB Output is correct
4 Correct 439 ms 268020 KB Output is correct
5 Correct 406 ms 268164 KB Output is correct
6 Correct 448 ms 267908 KB Output is correct
7 Correct 483 ms 267908 KB Output is correct
8 Correct 465 ms 267904 KB Output is correct
9 Correct 361 ms 268204 KB Output is correct
10 Correct 435 ms 268192 KB Output is correct
11 Correct 432 ms 267932 KB Output is correct
12 Correct 795 ms 268152 KB Output is correct
13 Correct 737 ms 267904 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5720 KB Output is correct
2 Correct 404 ms 269188 KB Output is correct
3 Correct 464 ms 269468 KB Output is correct
4 Correct 439 ms 268020 KB Output is correct
5 Correct 406 ms 268164 KB Output is correct
6 Correct 448 ms 267908 KB Output is correct
7 Correct 483 ms 267908 KB Output is correct
8 Correct 465 ms 267904 KB Output is correct
9 Correct 361 ms 268204 KB Output is correct
10 Correct 435 ms 268192 KB Output is correct
11 Correct 432 ms 267932 KB Output is correct
12 Correct 795 ms 268152 KB Output is correct
13 Correct 737 ms 267904 KB Output is correct
14 Correct 7 ms 5724 KB Output is correct
15 Correct 410 ms 268140 KB Output is correct
16 Correct 431 ms 267912 KB Output is correct
17 Correct 427 ms 268368 KB Output is correct
18 Correct 425 ms 268112 KB Output is correct
19 Correct 461 ms 267904 KB Output is correct
20 Correct 430 ms 268008 KB Output is correct
21 Correct 490 ms 267900 KB Output is correct
22 Correct 426 ms 267904 KB Output is correct
23 Correct 533 ms 268120 KB Output is correct
24 Correct 612 ms 267940 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5720 KB Output is correct
2 Correct 404 ms 269188 KB Output is correct
3 Correct 464 ms 269468 KB Output is correct
4 Correct 439 ms 268020 KB Output is correct
5 Correct 406 ms 268164 KB Output is correct
6 Correct 448 ms 267908 KB Output is correct
7 Correct 483 ms 267908 KB Output is correct
8 Correct 465 ms 267904 KB Output is correct
9 Correct 361 ms 268204 KB Output is correct
10 Correct 435 ms 268192 KB Output is correct
11 Correct 432 ms 267932 KB Output is correct
12 Correct 795 ms 268152 KB Output is correct
13 Correct 737 ms 267904 KB Output is correct
14 Correct 7 ms 5724 KB Output is correct
15 Correct 410 ms 268140 KB Output is correct
16 Correct 431 ms 267912 KB Output is correct
17 Correct 427 ms 268368 KB Output is correct
18 Correct 425 ms 268112 KB Output is correct
19 Correct 461 ms 267904 KB Output is correct
20 Correct 430 ms 268008 KB Output is correct
21 Correct 490 ms 267900 KB Output is correct
22 Correct 426 ms 267904 KB Output is correct
23 Correct 533 ms 268120 KB Output is correct
24 Correct 612 ms 267940 KB Output is correct
25 Correct 322 ms 267168 KB Output is correct
26 Correct 451 ms 267908 KB Output is correct
27 Correct 411 ms 267908 KB Output is correct
28 Correct 399 ms 267908 KB Output is correct
29 Correct 431 ms 267904 KB Output is correct
30 Correct 470 ms 268116 KB Output is correct
31 Correct 469 ms 267908 KB Output is correct
32 Correct 541 ms 267908 KB Output is correct
33 Correct 542 ms 268004 KB Output is correct
34 Correct 881 ms 267904 KB Output is correct
35 Correct 469 ms 267908 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5720 KB Output is correct
2 Runtime error 3087 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -