Submission #1089002

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089002		StefanSebez	Dungeons Game (IOI21_dungeons)	C++17	25 / 100	338 ms	170440 KiB

dungeons

#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=4e5+50,lg=28;
ll inf=1e18;
ll n,s[N],p[N],w[N],l[N],maks;
//ll par[N][lg+1],par1[N][lg+1],sum[N][lg+1],sum1[N][lg+1];
ll par[N][lg+1][7],sum[N][lg+1][7];
vector<ll>Vals;
//int IND(int x){for(int i=0;i<Vals.size();i++) if(Vals[i]==x) return i;}
void init(int n1, std::vector<int> s1, std::vector<int> p1, std::vector<int> w1, std::vector<int> l1) {
	n=n1;
	for(int i=0;i<n;i++){s[i]=s1[i],p[i]=p1[i],w[i]=w1[i],l[i]=l1[i];maks=max(maks,s[i]);Vals.pb(s[i]);}
	sort(Vals.begin(),Vals.end());
	int mmm=unique(Vals.begin(),Vals.end())-Vals.begin();
	Vals.resize(mmm);
	//for(auto i:Vals) printf("%lld ",i);printf("\n");
	if(Vals.size()<=5){
		for(int i=0;i<n;i++){
			/*par[i][0]=w[i];
			par1[i][0]=l[i];
			sum[i][0]=p[i];*/
			for(int j=0;j<=Vals.size();j++){
				ll R=inf;if(j!=Vals.size()) R=Vals[j];
				if(s[i]<R){
					par[i][0][j]=w[i];
					sum[i][0][j]=s[i];
				}
				else{
					par[i][0][j]=l[i];
					sum[i][0][j]=p[i];
				}
			}
		}
		for(int i=0;i<=lg;i++) for(int j=0;j<=5;j++) par[n][i][j]=n;
		for(int j=1;j<=lg;j++){
			for(int i=0;i<n;i++){
				for(int k=0;k<=Vals.size();k++){
					par[i][j][k]=par[par[i][j-1][k]][j-1][k];
					sum[i][j][k]=sum[i][j-1][k]+sum[par[i][j-1][k]][j-1][k];
				}
			}
		}
	}
	//for(int j=1;j<=lg;j++) for(int i=0;i<n;i++){par[i][j]=par[par[i][j-1]][j-1];par1[i][j]=par1[par1[i][j-1]][j-1];sum[i][j]=sum[i][j-1]+sum[par1[i][j-1]][j-1];}
	//for(int i=0;i<=n;i++) for(int j=0;j<=5;j++) printf("%i %i: %lld %lld %lld\n",i,j,par[i][j],par1[i][j],sum[i][j]);
	return;
}

long long simulate(int x, int z) {
	ll Z=z;
	/*for(int i=lg;i>=0;i--){
		if(Z+sum[x][i]<s[0] && par1[x][i]<n){
			Z+=sum[x][i];
			x=par1[x][i];
		}
	}
	if(Z<s[x]){
		Z+=p[x];
		x=l[x];
	}*/
	/*for(int i=lg;i>=0;i--){
		if(par[x][i]<n){
			ll val=(ll)1<<i;
			Z+=sum[x][i];
			x=par[x][i];
		}
	}
	if(x<n){
		Z+=s[x];
		x=w[x];
	}*/
	if(Vals.size()<=5){
		for(int k=0;k<=Vals.size();k++){
			ll R=inf;if(k!=Vals.size()) R=Vals[k];
			//printf("|%i %lld\n",k,R);
			for(int i=lg;i>=0;i--){
				//printf("%i %i %i: %lld %lld %lld %lld\n",x,i,k,par[x][i][k],sum[x][i][k],Z+sum[x][i][k],R);
				if(par[x][i][k]<n && Z+sum[x][i][k]<R){
					Z+=sum[x][i][k];
					x=par[x][i][k];
					//printf("da\n");
				}
			}
			//printf("*%i %lld\n",x,Z);
			if(x<n && Z<R){
				if(Z>=s[x]){
					Z+=s[x];
					x=w[x];
				}
				else{
					Z+=p[x];
					x=l[x];
				}
			}
			//printf("*%i %lld\n",x,Z);
		}
	}
	else{
		while(x<n && Z<maks){
			if(Z>=s[x]){
				Z+=s[x];
				x=w[x];
			}
			else{
				Z+=p[x];
				x=l[x];
			}
			//printf("*%i %lld\n",x,Z);
		}
	}
	return Z;
}

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:28:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |    for(int j=0;j<=Vals.size();j++){
      |                ~^~~~~~~~~~~~~
dungeons.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     ll R=inf;if(j!=Vals.size()) R=Vals[j];
      |                 ~^~~~~~~~~~~~~
dungeons.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int k=0;k<=Vals.size();k++){
      |                 ~^~~~~~~~~~~~~
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:79:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for(int k=0;k<=Vals.size();k++){
      |               ~^~~~~~~~~~~~~
dungeons.cpp:80:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |    ll R=inf;if(k!=Vals.size()) R=Vals[k];
      |                ~^~~~~~~~~~~~~

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