oj.uz

Submission #1051223

# Submission time Handle Problem Language Result Execution time Memory
1051223 2024-08-10T00:45:35 Z Edu175 Dungeons Game (IOI21_dungeons) C++17
63 / 100
 1148 ms 731728 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b; i<ioi; i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) {for(auto kdfhg:v)cout<<kdfhg<<" ";cout<<"\n";}
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll K=25,VK=25,MAXN=5e4+5,INF=1e18;
ll sub=1;
ll n;
ll s[MAXN],p[MAXN],w[MAXN],l[MAXN];

ii oper(ii a, ii b){
	return {max(min((ll)a.fst,b.fst-a.snd),-1ll),min(a.snd+b.snd,INF)};
}
struct bloque{
	ll pot;
	ll a[MAXN],v[MAXN];
	int F[K][MAXN];
	ii V[K][MAXN];
	void init(ll _pot){
		pot=_pot;
		fore(i,0,n){
			if(pot<s[i]){
				a[i]=l[i];
				v[i]=p[i];
			}
			else {
				a[i]=w[i];
				v[i]=s[i];
			}
		}
		fore(i,0,n){
			F[0][i]=a[i];
			V[0][i]={(pot<s[i]?s[i]:INF),v[i]};
			// if(a[i]==n)V[0][i].fst=-1;
		}
		F[0][n]=n;
		V[0][n]={-1,0};
		fore(k,1,K)fore(x,0,n+1){
			F[k][x]=F[k-1][F[k-1][x]];
			V[k][x]=oper(V[k-1][x],V[k-1][F[k-1][x]]);
		}
		// cout<<"bloque "<<pot<<":\n";
		// fore(i,0,n)cout<<a[i]<<" ";;cout<<"\n";
		// fore(i,0,n)cout<<v[i]<<" ";;cout<<"\n";
		// fore(i,0,n)cout<<V[0][i].fst<<","<<V[0][i].snd<<" ";;cout<<"\n";
	}
	void go(ll &x, ll &z){
		// cout<<"go "<<x<<" "<<z<<endl;
		assert(z<INF);
		ii nod={INF,0};
		for(ll k=K-1;k>=0;k--){
			auto nodi=oper(nod,V[k][x]);
			if(z<nodi.fst&&F[k][x]<n){
				// nod=nodi;
				z+=nodi.snd;
				// cout<<"salto "<<k<<"\n";
				// cout<<x<<" -> "<<F[k][x]<<"\n";
				// cout<<nod.fst<<","<<nod.snd<<"\n";
				assert(z<INF);
				x=F[k][x];
			}
		}
		// nod=oper(nod,V[0][x]);
		// cout<<"salto final"<<"\n";
		// cout<<x<<" -> "<<F[0][x]<<"\n";
		// cout<<nod.fst<<","<<nod.snd<<"\n";
		// x=F[0][x];
		// z+=nod.snd;
		// cout<<"ended in "<<x<<","<<z<<endl;
		// assert((pot<s[x]&&z>=s[x]));
		if((pot>=s[x]||z<s[x])&&a[x]==n){
			z+=v[x]; x=a[x];
			assert(x==n);
		}
		else {
			assert(pot<s[x]&&z>=s[x]);
			z+=s[x]; x=w[x];
		}
		// cout<<x<<" "<<z<<"\n\n";
	}
};
bloque dat[VK];
const ll MAXN2=4e5+5;
ll F[K][MAXN2];
ii V[K][MAXN2];
ii oper2(ii a, ii b){
	return {max((ll)a.fst,b.fst-a.snd),min(a.snd+b.snd,INF)};
}
void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L){
	n=N;
	fore(i,0,n){
		s[i]=S[i];
		p[i]=P[i];
		w[i]=W[i];
		l[i]=L[i];
	}
	fore(i,0,VK)dat[i].init(1ll<<i);
	// D.resize(n+1);
	// for(ll i=n-1;i>=0;i--){
	// 	D[i]=D[w[i]]+s[i];
	// 	sub&=s[i]==p[i];
	// }
	fore(i,0,n){
		sub&=s[i]==p[i];
		F[0][i]=w[i];
		V[0][i]={s[i],s[i]};
		// if(a[i]==n)V[0][i].fst=-1;
	}
	F[0][n]=n;
	V[0][n]={INF,0};
	fore(k,1,K)fore(x,0,n+1){
		F[k][x]=F[k-1][F[k-1][x]];
		V[k][x]=oper2(V[k-1][x],V[k-1][F[k-1][x]]);
	}
}
void go(ll &x, ll &z){
	for(ll k=K-1;k>=0;k--){
		auto nod=V[k][x];
		if(z>=nod.fst&&F[k][x]<n){
			z+=nod.snd;
			x=F[k][x];
		}
	}
	if(z>=s[x]){
		z+=s[x]; x=w[x];
		while(w[x]!=n);
	}
	else {
		z+=p[x]; x=l[x];
	}
}
long long simulate(int X, int Z){
	ll x=X,z=Z;
	
	if(sub){
		while(x<n)go(x,z);
		return z;
	}
	
	while(x<n){
		ll bl=min(VK-1,ll(63-__builtin_clzll(z)));
		dat[bl].go(x,z);
	}
	return z;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 493296 KB Output is correct
2 Correct 136 ms 493140 KB Output is correct
3 Correct 136 ms 500156 KB Output is correct
4 Correct 271 ms 665424 KB Output is correct
5 Correct 143 ms 500308 KB Output is correct
6 Correct 286 ms 665332 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 496720 KB Output is correct
2 Runtime error 350 ms 731728 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 496720 KB Output is correct
2 Correct 305 ms 666784 KB Output is correct
3 Correct 324 ms 666876 KB Output is correct
4 Correct 290 ms 666380 KB Output is correct
5 Correct 280 ms 666196 KB Output is correct
6 Correct 316 ms 666560 KB Output is correct
7 Correct 319 ms 666452 KB Output is correct
8 Correct 295 ms 666192 KB Output is correct
9 Correct 293 ms 666192 KB Output is correct
10 Correct 294 ms 665936 KB Output is correct
11 Correct 328 ms 666380 KB Output is correct
12 Correct 381 ms 666568 KB Output is correct
13 Correct 319 ms 666304 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 496720 KB Output is correct
2 Correct 305 ms 666784 KB Output is correct
3 Correct 324 ms 666876 KB Output is correct
4 Correct 290 ms 666380 KB Output is correct
5 Correct 280 ms 666196 KB Output is correct
6 Correct 316 ms 666560 KB Output is correct
7 Correct 319 ms 666452 KB Output is correct
8 Correct 295 ms 666192 KB Output is correct
9 Correct 293 ms 666192 KB Output is correct
10 Correct 294 ms 665936 KB Output is correct
11 Correct 328 ms 666380 KB Output is correct
12 Correct 381 ms 666568 KB Output is correct
13 Correct 319 ms 666304 KB Output is correct
14 Correct 136 ms 496844 KB Output is correct
15 Correct 316 ms 666824 KB Output is correct
16 Correct 314 ms 666704 KB Output is correct
17 Correct 293 ms 666300 KB Output is correct
18 Correct 290 ms 666492 KB Output is correct
19 Correct 361 ms 666448 KB Output is correct
20 Correct 304 ms 666100 KB Output is correct
21 Correct 305 ms 666192 KB Output is correct
22 Correct 315 ms 666180 KB Output is correct
23 Correct 336 ms 666452 KB Output is correct
24 Correct 395 ms 666344 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 496720 KB Output is correct
2 Correct 305 ms 666784 KB Output is correct
3 Correct 324 ms 666876 KB Output is correct
4 Correct 290 ms 666380 KB Output is correct
5 Correct 280 ms 666196 KB Output is correct
6 Correct 316 ms 666560 KB Output is correct
7 Correct 319 ms 666452 KB Output is correct
8 Correct 295 ms 666192 KB Output is correct
9 Correct 293 ms 666192 KB Output is correct
10 Correct 294 ms 665936 KB Output is correct
11 Correct 328 ms 666380 KB Output is correct
12 Correct 381 ms 666568 KB Output is correct
13 Correct 319 ms 666304 KB Output is correct
14 Correct 136 ms 496844 KB Output is correct
15 Correct 316 ms 666824 KB Output is correct
16 Correct 314 ms 666704 KB Output is correct
17 Correct 293 ms 666300 KB Output is correct
18 Correct 290 ms 666492 KB Output is correct
19 Correct 361 ms 666448 KB Output is correct
20 Correct 304 ms 666100 KB Output is correct
21 Correct 305 ms 666192 KB Output is correct
22 Correct 315 ms 666180 KB Output is correct
23 Correct 336 ms 666452 KB Output is correct
24 Correct 395 ms 666344 KB Output is correct
25 Correct 281 ms 665604 KB Output is correct
26 Correct 318 ms 666940 KB Output is correct
27 Correct 325 ms 666196 KB Output is correct
28 Correct 322 ms 666404 KB Output is correct
29 Correct 325 ms 666704 KB Output is correct
30 Correct 322 ms 666708 KB Output is correct
31 Correct 323 ms 666028 KB Output is correct
32 Correct 418 ms 666164 KB Output is correct
33 Correct 429 ms 666452 KB Output is correct
34 Correct 1148 ms 666284 KB Output is correct
35 Correct 400 ms 666196 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 496720 KB Output is correct
2 Runtime error 350 ms 731728 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -