Submission #1058822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058822		pcc	Dungeons Game (IOI21_dungeons)	C++17	25 / 100	569 ms	1265804 KiB

dungeons

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

#define ll long long
#define pii pair<int,int>
#define fs first
#define sc second
#define pll pair<ll,ll>

const int B = 24;
const int mxn = 4e5+10;

int par[mxn][B];
ll dp[mxn][B];
ll sum[mxn][B];
ll pref[mxn];
int N;
int str[mxn],win[mxn],lose[mxn],cost[mxn];

struct JELLY{
	int par[mxn][B];
	ll sum[mxn][B];
	JELLY(){
		memset(par,-1,sizeof(par));
		memset(sum,0,sizeof(sum));
	}
	void build(){
		for(int i = 1;i<B;i++){
			for(int j = 0;j<N;j++){
				int pre = par[j][i-1];
				if(pre == -1)continue;
				par[j][i] = par[par[j][i-1]][i-1];
				sum[j][i] = sum[j][i-1]+sum[pre][i-1];
			}
		}
		return;
	}
};

vector<ll> all;
JELLY jel[6];

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
	for(auto &i:s)all.push_back(i);
	all.push_back(0);
	sort(all.begin(),all.end());all.resize(unique(all.begin(),all.end())-all.begin());
	memset(par,-1,sizeof(par));
	N = n;
	for(int i = 0;i<N;i++){
		str[i] = s[i];
		cost[i] = p[i];
		win[i] = w[i];
		lose[i] = l[i];
	}
	win[N] = lose[N] = N;
	for(int i = 0;i<B;i++){
		par[N][i] = -1;
	}
	for(int i = N-1;i>=0;i--){
		pref[i] = str[i]+pref[win[i]];
		dp[i][0] = str[i]+pref[i];
		par[i][0] = win[i];
		sum[i][0] = str[i];
		for(int j = 1;j<B;j++){
			int pre = par[i][j-1];
			if(pre == -1)continue;
			par[i][j] = par[par[i][j-1]][j-1];
			dp[i][j] = max(dp[i][j-1],dp[par[i][j-1]][j-1]);
			sum[i][j] = sum[i][j-1]+sum[par[i][j-1]][j-1];
		}
	}
	for(int i = 0;i<N;i++){
		int p = lower_bound(all.begin(),all.end(),str[i])-all.begin();
		for(int j = 0;j<all.size();j++){
			if(j>=p)jel[j].par[i][0] = win[i],jel[j].sum[i][0] = str[i];
			else jel[j].par[i][0] = lose[i],jel[j].sum[i][0] = cost[i];
		}
	}
	for(auto &i:jel)i.build();
	all.push_back(LLONG_MAX);
	/*
	cerr<<"PAR: "<<endl;for(int i = 0;i<N;i++){
		for(int j = 0;j<B;j++)cerr<<par[i][j]<<' ';cerr<<endl;
	}
	cerr<<"DP: "<<endl;for(int i = 0;i<N;i++){
		for(int j = 0;j<B;j++)cerr<<dp[i][j]<<' ';cerr<<endl;
	}
	cerr<<"SUM: "<<endl;for(int i = 0;i<N;i++){
		for(int j = 0;j<B;j++)cerr<<sum[i][j]<<' ';cerr<<endl;
	}
	cerr<<"PREF: "<<endl;for(int i = 0;i<=N;i++)cerr<<pref[i]<<' ';cerr<<endl;
	cerr<<"JEL PAR: "<<endl;for(int i = 0;i<N;i++){
		for(int j = 0;j<B;j++)cerr<<jel.par[i][j]<<' ';cerr<<endl;
	}
	*/
	return;
}

long long simulate(int x, int z) {
	int now = x;
	ll val = z;
	for(int i = 0;i+1<all.size();i++){
		if(val>=all[i+1])continue;
		//cerr<<"IN: "<<all[i]<<','<<all[i+1]<<":"<<now<<','<<val<<endl;
		for(int j = B-1;j>=0;j--){
			int pre = jel[i].par[now][j];
			if(pre == -1)continue;
			if(val+jel[i].sum[now][j]<all[i+1]){
				val += jel[i].sum[now][j];
				now = jel[i].par[now][j];
				//cerr<<"JUMP: "<<i<<' '<<j<<' '<<now<<' '<<val<<endl;
			}
		}
		if(now == N)break;
		if(val<all[i+1]){
			val += jel[i].sum[now][0];
			now = jel[i].par[now][0];
			//cerr<<"JUMP: "<<i<<' '<<0<<' '<<now<<' '<<val<<endl;
		}
		if(now == N)break;
	}
	return val;
}

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for(int j = 0;j<all.size();j++){
      |                 ~^~~~~~~~~~~
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:104:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |  for(int i = 0;i+1<all.size();i++){
      |                ~~~^~~~~~~~~~~

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