Submission #1224122

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224122		Gabriel	Dungeons Game (IOI21_dungeons)	C++20	11 / 100	7092 ms	479488 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
struct Mazmorra{
	long long Fuerza, Fuerza_al_perder, Ir_al_ganar, Ir_al_perder;
};
struct Ancestro{
	long long Suma, Ir;
};
vector<Mazmorra> Mazmorras;
vector<long long> Para_ganar;
vector< vector<Ancestro> > Ancestros;
long long n;
bool _3 = 1;
vector< vector<long long> > Grafo;
long long La_fuerza_com_n;
void init(int N, vector<int> s, vector<int> p, vector<int> w, vector<int> l){
	n = N;
	Grafo.assign(n + 1, {});
	Para_ganar.assign(n + 1, 2222222222222222);
	Ancestros.assign(n + 1, {});
	long long Hola = -2;
	for(long long i = 0; i <= n; i++){
		Mazmorra Nueva;
		if(i == n){
			Nueva.Fuerza = 0;
			Nueva.Fuerza_al_perder = 0;
			Nueva.Ir_al_ganar = n;
			Nueva.Ir_al_perder = n;
			Mazmorras.push_back(Nueva);
			Ancestro Nuevo;
			Nuevo.Ir = n;
			Nuevo.Suma = 0;
			Ancestros[i].push_back(Nuevo);
			break;
		}
		La_fuerza_com_n = s[i];
		Nueva.Fuerza = s[i];
		Nueva.Fuerza_al_perder = p[i];
		Nueva.Ir_al_ganar = w[i];
		Nueva.Ir_al_perder = l[i];
		Ancestro Nuevo;
		Nuevo.Ir = l[i];
		Nuevo.Suma = p[i];
		Ancestros[i].push_back(Nuevo);
		Mazmorras.push_back(Nueva);
		Grafo[w[i]].push_back(i);
		if(Hola == -2) Hola = s[i];
		else if(Hola != s[i]) _3 = 0;
	}
	Para_ganar[n] = 0;
	set< pair<long long, long long> > Cola;
	Cola.insert({0, n});
	while(!Cola.empty()){
		long long Nodo = (*Cola.begin()).second;
		long long Llegar = (*Cola.begin()).first;
		Cola.erase(Cola.begin());
		if(Llegar > Para_ganar[Nodo]) continue;
		for(auto E: Grafo[Nodo]){
			if(Para_ganar[E] > Para_ganar[Nodo] + Mazmorras[E].Fuerza){
				Para_ganar[E] = Para_ganar[Nodo] + Mazmorras[E].Fuerza;
				Cola.insert({Para_ganar[E], E});
			}
		}
	}
	for(long long Saltitos = 0; Saltitos < 44; Saltitos++){
		for(long long i = 0; i <= n; i++){
			Ancestro Nuevo;
			Nuevo.Ir = Ancestros[Ancestros[i][Saltitos].Ir][Saltitos].Ir;
			Nuevo.Suma = Ancestros[Ancestros[i][Saltitos].Ir][Saltitos].Suma + Ancestros[i][Saltitos].Suma;
			Ancestros[i].push_back(Nuevo);
		}
	}
}
long long simulate(int x, int z){
	if(_3){
		if(x == n) return z;
		if(z >= La_fuerza_com_n) return Para_ganar[x] + z;
		if(Ancestros[x][0].Suma + z >= La_fuerza_com_n) return simulate(Ancestros[x][0].Ir, Ancestros[x][0].Suma + z);
		for(long long i = 1; i < Ancestros[x].size(); i++){
			if(Ancestros[x][i].Suma + z >= La_fuerza_com_n) return simulate(Ancestros[x][i - 1].Ir, Ancestros[x][i - 1].Suma + z);
		}
	}
	if(x == n) return z;
	if(z < Mazmorras[x].Fuerza) return simulate(Mazmorras[x].Ir_al_perder, z + Mazmorras[x].Fuerza_al_perder);
	else return simulate(Mazmorras[x].Ir_al_ganar, z + Mazmorras[x].Fuerza);
}

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