oj.uz

Submission #1051222

# Submission time Handle Problem Language Result Execution time Memory
1051222 2024-08-10T00:43:21 Z Edu175 Dungeons Game (IOI21_dungeons) C++17
63 / 100
 1175 ms 728912 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]&&w[x]==n){
		z+=s[x]; x=w[x];
	}
	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 150 ms 493156 KB Output is correct
2 Correct 154 ms 493244 KB Output is correct
3 Correct 139 ms 500208 KB Output is correct
4 Correct 275 ms 664404 KB Output is correct
5 Correct 161 ms 500308 KB Output is correct
6 Correct 321 ms 665344 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 496716 KB Output is correct
2 Runtime error 348 ms 728912 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 142 ms 496692 KB Output is correct
2 Correct 382 ms 666948 KB Output is correct
3 Correct 336 ms 667088 KB Output is correct
4 Correct 284 ms 666432 KB Output is correct
5 Correct 286 ms 666284 KB Output is correct
6 Correct 350 ms 666448 KB Output is correct
7 Correct 335 ms 666572 KB Output is correct
8 Correct 297 ms 666192 KB Output is correct
9 Correct 294 ms 666268 KB Output is correct
10 Correct 296 ms 665936 KB Output is correct
11 Correct 327 ms 666300 KB Output is correct
12 Correct 395 ms 666448 KB Output is correct
13 Correct 326 ms 666380 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 496692 KB Output is correct
2 Correct 382 ms 666948 KB Output is correct
3 Correct 336 ms 667088 KB Output is correct
4 Correct 284 ms 666432 KB Output is correct
5 Correct 286 ms 666284 KB Output is correct
6 Correct 350 ms 666448 KB Output is correct
7 Correct 335 ms 666572 KB Output is correct
8 Correct 297 ms 666192 KB Output is correct
9 Correct 294 ms 666268 KB Output is correct
10 Correct 296 ms 665936 KB Output is correct
11 Correct 327 ms 666300 KB Output is correct
12 Correct 395 ms 666448 KB Output is correct
13 Correct 326 ms 666380 KB Output is correct
14 Correct 139 ms 496812 KB Output is correct
15 Correct 297 ms 666692 KB Output is correct
16 Correct 318 ms 666708 KB Output is correct
17 Correct 299 ms 666284 KB Output is correct
18 Correct 296 ms 666436 KB Output is correct
19 Correct 345 ms 666452 KB Output is correct
20 Correct 306 ms 666196 KB Output is correct
21 Correct 325 ms 666196 KB Output is correct
22 Correct 305 ms 666196 KB Output is correct
23 Correct 336 ms 666448 KB Output is correct
24 Correct 432 ms 666532 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 496692 KB Output is correct
2 Correct 382 ms 666948 KB Output is correct
3 Correct 336 ms 667088 KB Output is correct
4 Correct 284 ms 666432 KB Output is correct
5 Correct 286 ms 666284 KB Output is correct
6 Correct 350 ms 666448 KB Output is correct
7 Correct 335 ms 666572 KB Output is correct
8 Correct 297 ms 666192 KB Output is correct
9 Correct 294 ms 666268 KB Output is correct
10 Correct 296 ms 665936 KB Output is correct
11 Correct 327 ms 666300 KB Output is correct
12 Correct 395 ms 666448 KB Output is correct
13 Correct 326 ms 666380 KB Output is correct
14 Correct 139 ms 496812 KB Output is correct
15 Correct 297 ms 666692 KB Output is correct
16 Correct 318 ms 666708 KB Output is correct
17 Correct 299 ms 666284 KB Output is correct
18 Correct 296 ms 666436 KB Output is correct
19 Correct 345 ms 666452 KB Output is correct
20 Correct 306 ms 666196 KB Output is correct
21 Correct 325 ms 666196 KB Output is correct
22 Correct 305 ms 666196 KB Output is correct
23 Correct 336 ms 666448 KB Output is correct
24 Correct 432 ms 666532 KB Output is correct
25 Correct 299 ms 665668 KB Output is correct
26 Correct 330 ms 666788 KB Output is correct
27 Correct 306 ms 666352 KB Output is correct
28 Correct 338 ms 666432 KB Output is correct
29 Correct 345 ms 666688 KB Output is correct
30 Correct 319 ms 666444 KB Output is correct
31 Correct 323 ms 666116 KB Output is correct
32 Correct 414 ms 666388 KB Output is correct
33 Correct 444 ms 666352 KB Output is correct
34 Correct 1175 ms 666192 KB Output is correct
35 Correct 398 ms 666460 KB Output is correct

Subtask #6
0.0 / 11.0

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