Submission #621105

#	Time	Username	Problem	Language	Result	Execution time	Memory
621105		amunduzbaev	Dungeons Game (IOI21_dungeons)	C++17	25 / 100	319 ms	257876 KiB

dungeons

#include "dungeons.h"
#ifndef EVAL
#include "grader.cpp"
#endif

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

typedef long long ll;
const int N = 4e5 + 5;
const int M = 25;
vector<ll> v,  edges[6][N];
ll s[N], p[N], w[N], l[N], n;
ll par[6][N][M], sum[6][N][M];

void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L) {
	n = N;
	for(int i=0;i<n;i++){
		s[i] = S[i], p[i] = P[i], w[i] = W[i], l[i] = L[i];
		v.push_back(s[i]);
	}
	w[n] = l[n] = n;
	
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	v.push_back(1e18);
	
	//~ for(auto x : v) cout<<x<<" ";
	//~ cout<<"\n";
	
	for(int k=0;k<(int)v.size();k++){
		for(int i=0;i<=n;i++){
			if(s[i] < v[k]) par[k][i][0] = w[i], sum[k][i][0] = s[i];
			else par[k][i][0] = l[i], sum[k][i][0] = p[i];
		}
		
		for(int j=1;j<M;j++){
			for(int i=0;i<=n;i++){
				par[k][i][j] = par[k][par[k][i][j-1]][j-1];
				sum[k][i][j] = sum[k][i][j-1] + sum[k][par[k][i][j-1]][j-1];
			}
		}
	}
}

ll simulate(int x, int z) {
	ll res = z;
	for(int k=0;k<(int)v.size();k++){
		//~ cout<<v[k]<<" "<<res<<"\n";
		for(int j=M-1;~j;j--){
			if(res + sum[k][x][j] < v[k]){
				res += sum[k][x][j];
				x = par[k][x][j];
			}
		}
		
		if(res >= v[k]) continue;
		res += sum[k][x][0], x = par[k][x][0];
		//~ cout<<res<<"\n";
	}
	
	return res;
}

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