oj.uz

Submission #623297

# Submission time Handle Problem Language Result Execution time Memory
623297 2022-08-05T12:21:24 Z Koosha_mv Dungeons Game (IOI21_dungeons) C++17
100 / 100
 4191 ms 802864 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,int(v.size())) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=400400,lg=25,S=4;
const ll inf=1e18+99;

int n;
int par[S][N][lg];
ll Min[S][N][lg];
ll prt[S][N][lg];
vector<int> s,p,w,t;

void init(int _n,vector<int> _s,vector<int> _p,vector<int> _w,vector<int> _t) {
	n=_n;
	s=_s,p=_p,w=_w,t=_t;
	s.pb(1<<lg);
	w.pb(-1);
	t.pb(-1);
	p.pb(-1);
	f(l,0,S){
		f(i,0,n+1){
			if(s[i]<=(1<<(l<<3))){
				par[l][i][0]=w[i];
				prt[l][i][0]=s[i];
				Min[l][i][0]=inf;
			}
			else{
				par[l][i][0]=t[i];
				prt[l][i][0]=p[i];
				Min[l][i][0]=(i==n ? 0 : s[i]);
			}
		}
		f(j,1,lg){
			f(i,0,n+1){
				int nxt=par[l][i][j-1];
				par[l][i][j]=par[l][nxt][j-1];
				prt[l][i][j]=prt[l][i][j-1]+prt[l][nxt][j-1];

				if(Min[l][nxt][j-1]<inf){
					Min[l][i][j]=min(Min[l][i][j-1],(ll)(max(0ll,Min[l][nxt][j-1]-prt[l][i][j-1])));
				}
				else{
					Min[l][i][j]=Min[l][i][j-1];
				}
			}
		}
	}
}

ll simulate(int pos,int _val){
	int l=0;
	ll val=_val;
	while(1){
		while((1<<((l+1)<<3))<=val && l+1<S) l++;
		f_(i,lg-1,0){
			if(Min[l][pos][i]>val){
				val+=prt[l][pos][i];
				pos=par[l][pos][i];
			}
		}
		if(pos==n) break ;
		val+=s[pos];
		pos=w[pos];
	}
	return val;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 4 ms 4380 KB Output is correct
4 Correct 185 ms 100520 KB Output is correct
5 Correct 4 ms 4420 KB Output is correct
6 Correct 182 ms 100528 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2392 KB Output is correct
2 Correct 1677 ms 802732 KB Output is correct
3 Correct 1668 ms 802776 KB Output is correct
4 Correct 1601 ms 802628 KB Output is correct
5 Correct 1560 ms 802728 KB Output is correct
6 Correct 1875 ms 802608 KB Output is correct
7 Correct 2175 ms 802744 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2388 KB Output is correct
2 Correct 236 ms 101324 KB Output is correct
3 Correct 250 ms 101284 KB Output is correct
4 Correct 289 ms 101308 KB Output is correct
5 Correct 200 ms 101252 KB Output is correct
6 Correct 232 ms 101256 KB Output is correct
7 Correct 223 ms 101368 KB Output is correct
8 Correct 259 ms 101468 KB Output is correct
9 Correct 251 ms 101272 KB Output is correct
10 Correct 331 ms 101288 KB Output is correct
11 Correct 308 ms 101252 KB Output is correct
12 Correct 366 ms 101264 KB Output is correct
13 Correct 293 ms 101388 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2388 KB Output is correct
2 Correct 236 ms 101324 KB Output is correct
3 Correct 250 ms 101284 KB Output is correct
4 Correct 289 ms 101308 KB Output is correct
5 Correct 200 ms 101252 KB Output is correct
6 Correct 232 ms 101256 KB Output is correct
7 Correct 223 ms 101368 KB Output is correct
8 Correct 259 ms 101468 KB Output is correct
9 Correct 251 ms 101272 KB Output is correct
10 Correct 331 ms 101288 KB Output is correct
11 Correct 308 ms 101252 KB Output is correct
12 Correct 366 ms 101264 KB Output is correct
13 Correct 293 ms 101388 KB Output is correct
14 Correct 3 ms 2388 KB Output is correct
15 Correct 258 ms 101344 KB Output is correct
16 Correct 246 ms 101372 KB Output is correct
17 Correct 212 ms 101368 KB Output is correct
18 Correct 219 ms 101368 KB Output is correct
19 Correct 216 ms 101264 KB Output is correct
20 Correct 399 ms 101364 KB Output is correct
21 Correct 546 ms 101304 KB Output is correct
22 Correct 805 ms 101368 KB Output is correct
23 Correct 273 ms 101388 KB Output is correct
24 Correct 398 ms 101328 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2388 KB Output is correct
2 Correct 236 ms 101324 KB Output is correct
3 Correct 250 ms 101284 KB Output is correct
4 Correct 289 ms 101308 KB Output is correct
5 Correct 200 ms 101252 KB Output is correct
6 Correct 232 ms 101256 KB Output is correct
7 Correct 223 ms 101368 KB Output is correct
8 Correct 259 ms 101468 KB Output is correct
9 Correct 251 ms 101272 KB Output is correct
10 Correct 331 ms 101288 KB Output is correct
11 Correct 308 ms 101252 KB Output is correct
12 Correct 366 ms 101264 KB Output is correct
13 Correct 293 ms 101388 KB Output is correct
14 Correct 3 ms 2388 KB Output is correct
15 Correct 258 ms 101344 KB Output is correct
16 Correct 246 ms 101372 KB Output is correct
17 Correct 212 ms 101368 KB Output is correct
18 Correct 219 ms 101368 KB Output is correct
19 Correct 216 ms 101264 KB Output is correct
20 Correct 399 ms 101364 KB Output is correct
21 Correct 546 ms 101304 KB Output is correct
22 Correct 805 ms 101368 KB Output is correct
23 Correct 273 ms 101388 KB Output is correct
24 Correct 398 ms 101328 KB Output is correct
25 Correct 186 ms 100588 KB Output is correct
26 Correct 220 ms 101352 KB Output is correct
27 Correct 213 ms 101308 KB Output is correct
28 Correct 245 ms 101268 KB Output is correct
29 Correct 232 ms 101308 KB Output is correct
30 Correct 282 ms 101476 KB Output is correct
31 Correct 344 ms 101320 KB Output is correct
32 Correct 440 ms 101364 KB Output is correct
33 Correct 625 ms 101328 KB Output is correct
34 Correct 853 ms 101416 KB Output is correct
35 Correct 1148 ms 101348 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2392 KB Output is correct
2 Correct 1677 ms 802732 KB Output is correct
3 Correct 1668 ms 802776 KB Output is correct
4 Correct 1601 ms 802628 KB Output is correct
5 Correct 1560 ms 802728 KB Output is correct
6 Correct 1875 ms 802608 KB Output is correct
7 Correct 2175 ms 802744 KB Output is correct
8 Correct 2 ms 2388 KB Output is correct
9 Correct 236 ms 101324 KB Output is correct
10 Correct 250 ms 101284 KB Output is correct
11 Correct 289 ms 101308 KB Output is correct
12 Correct 200 ms 101252 KB Output is correct
13 Correct 232 ms 101256 KB Output is correct
14 Correct 223 ms 101368 KB Output is correct
15 Correct 259 ms 101468 KB Output is correct
16 Correct 251 ms 101272 KB Output is correct
17 Correct 331 ms 101288 KB Output is correct
18 Correct 308 ms 101252 KB Output is correct
19 Correct 366 ms 101264 KB Output is correct
20 Correct 293 ms 101388 KB Output is correct
21 Correct 3 ms 2388 KB Output is correct
22 Correct 258 ms 101344 KB Output is correct
23 Correct 246 ms 101372 KB Output is correct
24 Correct 212 ms 101368 KB Output is correct
25 Correct 219 ms 101368 KB Output is correct
26 Correct 216 ms 101264 KB Output is correct
27 Correct 399 ms 101364 KB Output is correct
28 Correct 546 ms 101304 KB Output is correct
29 Correct 805 ms 101368 KB Output is correct
30 Correct 273 ms 101388 KB Output is correct
31 Correct 398 ms 101328 KB Output is correct
32 Correct 186 ms 100588 KB Output is correct
33 Correct 220 ms 101352 KB Output is correct
34 Correct 213 ms 101308 KB Output is correct
35 Correct 245 ms 101268 KB Output is correct
36 Correct 232 ms 101308 KB Output is correct
37 Correct 282 ms 101476 KB Output is correct
38 Correct 344 ms 101320 KB Output is correct
39 Correct 440 ms 101364 KB Output is correct
40 Correct 625 ms 101328 KB Output is correct
41 Correct 853 ms 101416 KB Output is correct
42 Correct 1148 ms 101348 KB Output is correct
43 Correct 0 ms 340 KB Output is correct
44 Correct 2 ms 2388 KB Output is correct
45 Correct 1789 ms 802628 KB Output is correct
46 Correct 1497 ms 802860 KB Output is correct
47 Correct 1972 ms 802828 KB Output is correct
48 Correct 1541 ms 802744 KB Output is correct
49 Correct 1696 ms 802860 KB Output is correct
50 Correct 1610 ms 802844 KB Output is correct
51 Correct 1545 ms 802752 KB Output is correct
52 Correct 1659 ms 802620 KB Output is correct
53 Correct 2412 ms 802616 KB Output is correct
54 Correct 2259 ms 802636 KB Output is correct
55 Correct 2716 ms 802712 KB Output is correct
56 Correct 3786 ms 802624 KB Output is correct
57 Correct 2907 ms 802612 KB Output is correct
58 Correct 2969 ms 802728 KB Output is correct
59 Correct 2693 ms 802736 KB Output is correct
60 Correct 4191 ms 802712 KB Output is correct
61 Correct 3774 ms 802864 KB Output is correct