Submission #609377

#	Time	Username	Problem	Language	Result	Execution time	Memory
609377		FatihSolak	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	7024 ms	310068 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
#define N 400005
#define M 50005
#define K 30
#define X 10
using namespace std;
struct node2{
	int to;
	long long sum;
	long long maxi;
};
node2 sp2[N][K];
int n;
bool subtask2 = 1;
vector<int> s,p,w,l;
void init(int n_, vector<int> s_, vector<int> p_, vector<int> w_, vector<int> l_) {
	n = n_;
	s = s_;
	p = p_;
	w = w_;
	l = l_;
	for(int i = 0;i<n;i++){
		subtask2 &= (s[i] == p[i]);
	}
	if(subtask2){
		for(int i = 0;i<n;i++){
			sp2[i][0].to = w[i];
			sp2[i][0].sum = s[i];
			sp2[i][0].maxi = s[i];
		}
		sp2[n][0].to = n;
		sp2[n][0].sum = 0;
		sp2[n][0].maxi = 0;
		for(int j = 1;j<K;j++){
			for(int i = 0;i<=n;i++){
				sp2[i][j].to = sp2[sp2[i][j-1].to][j-1].to;
				sp2[i][j].sum = sp2[i][j-1].sum + sp2[sp2[i][j-1].to][j-1].sum;
				sp2[i][j].maxi = max(sp2[i][j-1].maxi,sp2[sp2[i][j-1].to][j-1].maxi - sp2[i][j-1].sum);
			}
		}
	}
	return;
}

long long simulate(int x, int z) {
	long long pw = z;
	if(subtask2){
		while(x != n){
			for(int i = K-1;i>=0;i--){
				if(sp2[x][i].maxi <= pw){
					pw += sp2[x][i].sum;
					x = sp2[x][i].to;
				}
			}
			if(x != n){
				pw += p[x];
				x = l[x];
			}
		}	
		return pw;
	}
	while(x != n){
		if(s[x] <= pw){
			pw += s[x];
			x = w[x];
		}
		else{
			pw += p[x];
			x = l[x];
		}
	}
	return pw;
}

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