oj.uz

Submission #1049942

# Submission time Handle Problem Language Result Execution time Memory
1049942 2024-08-09T06:16:08 Z Alihan_8 Dungeons Game (IOI21_dungeons) C++17
63 / 100
 3152 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 = 10;

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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 12 ms 13492 KB Output is correct
4 Correct 351 ms 327048 KB Output is correct
5 Correct 12 ms 13404 KB Output is correct
6 Correct 375 ms 326756 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7004 KB Output is correct
2 Runtime error 3152 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 7 ms 7004 KB Output is correct
2 Correct 585 ms 326644 KB Output is correct
3 Correct 549 ms 327068 KB Output is correct
4 Correct 517 ms 327996 KB Output is correct
5 Correct 561 ms 327808 KB Output is correct
6 Correct 567 ms 328188 KB Output is correct
7 Correct 557 ms 328104 KB Output is correct
8 Correct 537 ms 327804 KB Output is correct
9 Correct 433 ms 327856 KB Output is correct
10 Correct 512 ms 327508 KB Output is correct
11 Correct 523 ms 328024 KB Output is correct
12 Correct 988 ms 328336 KB Output is correct
13 Correct 887 ms 327940 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7004 KB Output is correct
2 Correct 585 ms 326644 KB Output is correct
3 Correct 549 ms 327068 KB Output is correct
4 Correct 517 ms 327996 KB Output is correct
5 Correct 561 ms 327808 KB Output is correct
6 Correct 567 ms 328188 KB Output is correct
7 Correct 557 ms 328104 KB Output is correct
8 Correct 537 ms 327804 KB Output is correct
9 Correct 433 ms 327856 KB Output is correct
10 Correct 512 ms 327508 KB Output is correct
11 Correct 523 ms 328024 KB Output is correct
12 Correct 988 ms 328336 KB Output is correct
13 Correct 887 ms 327940 KB Output is correct
14 Correct 6 ms 7000 KB Output is correct
15 Correct 478 ms 328180 KB Output is correct
16 Correct 510 ms 328372 KB Output is correct
17 Correct 555 ms 327812 KB Output is correct
18 Correct 543 ms 328044 KB Output is correct
19 Correct 546 ms 328044 KB Output is correct
20 Correct 553 ms 327796 KB Output is correct
21 Correct 612 ms 327892 KB Output is correct
22 Correct 553 ms 327756 KB Output is correct
23 Correct 696 ms 327988 KB Output is correct
24 Correct 837 ms 328108 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7004 KB Output is correct
2 Correct 585 ms 326644 KB Output is correct
3 Correct 549 ms 327068 KB Output is correct
4 Correct 517 ms 327996 KB Output is correct
5 Correct 561 ms 327808 KB Output is correct
6 Correct 567 ms 328188 KB Output is correct
7 Correct 557 ms 328104 KB Output is correct
8 Correct 537 ms 327804 KB Output is correct
9 Correct 433 ms 327856 KB Output is correct
10 Correct 512 ms 327508 KB Output is correct
11 Correct 523 ms 328024 KB Output is correct
12 Correct 988 ms 328336 KB Output is correct
13 Correct 887 ms 327940 KB Output is correct
14 Correct 6 ms 7000 KB Output is correct
15 Correct 478 ms 328180 KB Output is correct
16 Correct 510 ms 328372 KB Output is correct
17 Correct 555 ms 327812 KB Output is correct
18 Correct 543 ms 328044 KB Output is correct
19 Correct 546 ms 328044 KB Output is correct
20 Correct 553 ms 327796 KB Output is correct
21 Correct 612 ms 327892 KB Output is correct
22 Correct 553 ms 327756 KB Output is correct
23 Correct 696 ms 327988 KB Output is correct
24 Correct 837 ms 328108 KB Output is correct
25 Correct 386 ms 327436 KB Output is correct
26 Correct 512 ms 328532 KB Output is correct
27 Correct 510 ms 327864 KB Output is correct
28 Correct 481 ms 327808 KB Output is correct
29 Correct 514 ms 328320 KB Output is correct
30 Correct 588 ms 327892 KB Output is correct
31 Correct 587 ms 327808 KB Output is correct
32 Correct 660 ms 327552 KB Output is correct
33 Correct 682 ms 326600 KB Output is correct
34 Correct 932 ms 326532 KB Output is correct
35 Correct 612 ms 326780 KB Output is correct

Subtask #6
0.0 / 11.0

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