oj.uz

Submission #1049169

# Submission time Handle Problem Language Result Execution time Memory
1049169 2024-08-08T14:26:42 Z Alihan_8 Dungeons Game (IOI21_dungeons) C++17
37 / 100
 7000 ms 352624 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;

vector <vector<i64>> need, S, U;

int n;

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_;
	
	need.resize(n + 1);
	S.resize(n + 1); 
	U.resize(n + 1);
	
	for ( int i = 0; i <= n; i++ ){
		need[i].resize(L);
		S[i].resize(L);
		U[i].resize(L);
		
		if ( i == n ) continue;
		
		need[i][0] = s[i];
		S[i][0] = s[i];
		U[i][0] = w[i];
	}
	
	U[n][0] = n;
	
	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] = max(need[j][i - 1], need[U[j][i - 1]][i - 1] - S[j][i - 1]);
		}
	}
}

long long simulate(int x, int Z) {
	// subtask #2
	
	i64 z = Z;
	
	while ( x < n ){
		for ( int i = L - 1; i >= 0; i-- ){
			if ( U[x][i] != n && need[x][i] <= z ){
				z += S[x][i];
				x = U[x][i];
			}
		}
		
		if ( s[x] <= z ){
			z += s[x];
			x = w[x];
			
			continue;
		}
		
		if ( x == n ) break;
		
		z += p[x];
		x = l[x];
	}
	
	return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 2140 KB Output is correct
4 Correct 45 ms 43640 KB Output is correct
5 Correct 2 ms 2140 KB Output is correct
6 Correct 49 ms 43872 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 476 ms 352624 KB Output is correct
3 Correct 465 ms 348736 KB Output is correct
4 Correct 497 ms 348756 KB Output is correct
5 Correct 450 ms 348976 KB Output is correct
6 Correct 490 ms 349008 KB Output is correct
7 Correct 455 ms 349520 KB Output is correct

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 75 ms 45808 KB Output is correct
3 Correct 87 ms 45692 KB Output is correct
4 Correct 74 ms 44628 KB Output is correct
5 Correct 71 ms 44636 KB Output is correct
6 Execution timed out 7027 ms 44628 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 75 ms 45808 KB Output is correct
3 Correct 87 ms 45692 KB Output is correct
4 Correct 74 ms 44628 KB Output is correct
5 Correct 71 ms 44636 KB Output is correct
6 Execution timed out 7027 ms 44628 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 75 ms 45808 KB Output is correct
3 Correct 87 ms 45692 KB Output is correct
4 Correct 74 ms 44628 KB Output is correct
5 Correct 71 ms 44636 KB Output is correct
6 Execution timed out 7027 ms 44628 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB Output is correct
2 Correct 476 ms 352624 KB Output is correct
3 Correct 465 ms 348736 KB Output is correct
4 Correct 497 ms 348756 KB Output is correct
5 Correct 450 ms 348976 KB Output is correct
6 Correct 490 ms 349008 KB Output is correct
7 Correct 455 ms 349520 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 75 ms 45808 KB Output is correct
10 Correct 87 ms 45692 KB Output is correct
11 Correct 74 ms 44628 KB Output is correct
12 Correct 71 ms 44636 KB Output is correct
13 Execution timed out 7027 ms 44628 KB Time limit exceeded
14 Halted 0 ms 0 KB -