oj.uz

Submission #1049203

# Submission time Handle Problem Language Result Execution time Memory
1049203 2024-08-08T14:51:12 Z Alihan_8 Dungeons Game (IOI21_dungeons) C++17
25 / 100
 2627 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 = 30;

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

int n;

struct Jump{
	vector <vector<i64>> U, S;
	
	int n;
	
	Jump() {}
	
	void modify(vector <int> p, vector <int> w){
		n = p.size();
		
		S.resize(n + 1); 
		U.resize(n + 1);
		
		for ( int i = 0; i <= n; i++ ){
			S[i].resize(L);
			U[i].resize(L);
			
			if ( i == n ) continue;
			
			S[i][0] = w[i];
			U[i][0] = p[i];
		}
		
		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]);
			}
		}
	}
	
	i64 simulate(int &u, i64 z, i64 rq){
		i64 cnt = z;
		
		for ( int i = L - 1; i >= 0; i-- ){
			if ( cnt + S[u][i] < rq ){
				cnt += S[u][i];
				u = U[u][i];
			}
		}
		
		if ( cnt < rq && u != n ){
			cnt += S[u][0];
			u = U[u][0];
		}
		
		return cnt;
	};
};

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_;
	
	v.pb(inf);
	
	for ( auto &u: s ) v.pb(u);
	
	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);
		
		A.pb(h);
	}
}

long long simulate(int x, int Z) {
	// subtask #4
	
	i64 z = Z;
	
	for ( int i = 0; i < (int)v.size(); i++ ){
		z = A[i].simulate(x, z, v[i]);
	}
	
	assert(x == n);
	
	return z;
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 10 ms 13656 KB Output is correct
4 Runtime error 2078 ms 2097152 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 615 ms 550148 KB Output is correct
2 Runtime error 2627 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 2 ms 2136 KB Output is correct
2 Correct 118 ms 86512 KB Output is correct
3 Correct 124 ms 86432 KB Output is correct
4 Correct 115 ms 86436 KB Output is correct
5 Correct 114 ms 86384 KB Output is correct
6 Correct 108 ms 86436 KB Output is correct
7 Correct 109 ms 86440 KB Output is correct
8 Correct 122 ms 87396 KB Output is correct
9 Correct 112 ms 87456 KB Output is correct
10 Correct 116 ms 87300 KB Output is correct
11 Correct 114 ms 87712 KB Output is correct
12 Correct 179 ms 87736 KB Output is correct
13 Correct 170 ms 87684 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2136 KB Output is correct
2 Correct 118 ms 86512 KB Output is correct
3 Correct 124 ms 86432 KB Output is correct
4 Correct 115 ms 86436 KB Output is correct
5 Correct 114 ms 86384 KB Output is correct
6 Correct 108 ms 86436 KB Output is correct
7 Correct 109 ms 86440 KB Output is correct
8 Correct 122 ms 87396 KB Output is correct
9 Correct 112 ms 87456 KB Output is correct
10 Correct 116 ms 87300 KB Output is correct
11 Correct 114 ms 87712 KB Output is correct
12 Correct 179 ms 87736 KB Output is correct
13 Correct 170 ms 87684 KB Output is correct
14 Correct 3 ms 3676 KB Output is correct
15 Correct 191 ms 142664 KB Output is correct
16 Correct 262 ms 170384 KB Output is correct
17 Correct 295 ms 197244 KB Output is correct
18 Correct 306 ms 197268 KB Output is correct
19 Correct 240 ms 197280 KB Output is correct
20 Correct 218 ms 142240 KB Output is correct
21 Correct 288 ms 169756 KB Output is correct
22 Correct 150 ms 114852 KB Output is correct
23 Correct 262 ms 169992 KB Output is correct
24 Correct 321 ms 142404 KB Output is correct

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2136 KB Output is correct
2 Correct 118 ms 86512 KB Output is correct
3 Correct 124 ms 86432 KB Output is correct
4 Correct 115 ms 86436 KB Output is correct
5 Correct 114 ms 86384 KB Output is correct
6 Correct 108 ms 86436 KB Output is correct
7 Correct 109 ms 86440 KB Output is correct
8 Correct 122 ms 87396 KB Output is correct
9 Correct 112 ms 87456 KB Output is correct
10 Correct 116 ms 87300 KB Output is correct
11 Correct 114 ms 87712 KB Output is correct
12 Correct 179 ms 87736 KB Output is correct
13 Correct 170 ms 87684 KB Output is correct
14 Correct 3 ms 3676 KB Output is correct
15 Correct 191 ms 142664 KB Output is correct
16 Correct 262 ms 170384 KB Output is correct
17 Correct 295 ms 197244 KB Output is correct
18 Correct 306 ms 197268 KB Output is correct
19 Correct 240 ms 197280 KB Output is correct
20 Correct 218 ms 142240 KB Output is correct
21 Correct 288 ms 169756 KB Output is correct
22 Correct 150 ms 114852 KB Output is correct
23 Correct 262 ms 169992 KB Output is correct
24 Correct 321 ms 142404 KB Output is correct
25 Runtime error 1990 ms 2097152 KB Execution killed with signal 9
26 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

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