Submission #1184236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184236		hyakup	Dungeons Game (IOI21_dungeons)	C++20	0 / 100	1 ms	1352 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pll = pair<long long, long long>;


const int maxn = 4e5 + 10;
const int logn = 21;

pll pai[2][logn][maxn];
int N, S;

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
	S = s[0];
	N = n;
	for( int i = 0; i < logn; i++ ){
		for( int j = 0; j < n; j++ ){
			if( i == 0 ) pai[0][0][j] = pll( l[j], p[j] );
			else{
				auto [a, va] = pai[0][i - 1][j];
				auto [b, vb] = pai[0][i - 1][a];
				pai[0][i][j] = pll( b, va + vb );
			}
		}
		pai[0][i][n] = pll( n, 0 );
	}

	for( int i = 0; i < logn; i++ ){
		for( int j = 0; j < n; j++ ){
			if( i == 0 ) pai[1][0][j] = pll( w[j], s[j] );
			else{
				auto [a, va] = pai[1][i - 1][j];
				auto [b, vb] = pai[1][i - 1][a];
				pai[1][i][j] = pll( b, va + vb );
			}
		}
		pai[1][i][n] = pll( n, 0 ); 
	}

	return;
}

pll lift( int id, int val, int t ){
	if( t == 0 ){
		for( int i = logn - 1; i >= 0; i-- ){
			if( val + pai[t][i][id].second < S ){
				val += pai[t][i][id].second;
				id = pai[t][i][id].first;
			}
		}

		val += pai[t][0][id].second;
		id = pai[t][0][id].first;

		return pll( id, val );
	}
	else{
			for( int i = logn - 1; i >= 0; i-- ){
				if( pai[t][i][id].first < N ){
					val += pai[t][i][id].second;
					id = pai[t][i][id].first;
				}
			}

			val += pai[t][0][id].second;
			id = pai[t][0][id].first;

			return pll( id, val );
	}
}

long long simulate( int x, int z ) {
	auto [a, va] = lift( x, z, 0 );
	return lift( a, va, 1 ).second;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 26
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11