oj.uz

답안 #623296

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
623296 2022-08-05T12:18:54 Z Koosha_mv 던전 (IOI21_dungeons) C++17
100 / 100
 3961 ms 814364 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++;
		//cout<<pos<<" "<<val<<" -> "<<l<<endl;
		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 ;
		//cout<<"posval "<<pos<<" "<<val<<endl;
		val+=s[pos];
		pos=w[pos];
	}
	return val;
}
/*
3 2
2 6 9
3 1 2
2 2 3
1 0 1
0 1
2 3
*/

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 4 ms 4436 KB Output is correct
4 Correct 173 ms 100476 KB Output is correct
5 Correct 3 ms 4436 KB Output is correct
6 Correct 165 ms 100484 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2388 KB Output is correct
2 Correct 1717 ms 802716 KB Output is correct
3 Correct 1520 ms 809592 KB Output is correct
4 Correct 1542 ms 811168 KB Output is correct
5 Correct 1543 ms 811164 KB Output is correct
6 Correct 1953 ms 809516 KB Output is correct
7 Correct 2193 ms 807884 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2388 KB Output is correct
2 Correct 262 ms 101372 KB Output is correct
3 Correct 253 ms 101332 KB Output is correct
4 Correct 241 ms 101308 KB Output is correct
5 Correct 239 ms 101320 KB Output is correct
6 Correct 222 ms 101264 KB Output is correct
7 Correct 244 ms 101272 KB Output is correct
8 Correct 298 ms 101272 KB Output is correct
9 Correct 226 ms 101388 KB Output is correct
10 Correct 421 ms 101264 KB Output is correct
11 Correct 272 ms 101368 KB Output is correct
12 Correct 353 ms 101324 KB Output is correct
13 Correct 255 ms 101364 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2388 KB Output is correct
2 Correct 262 ms 101372 KB Output is correct
3 Correct 253 ms 101332 KB Output is correct
4 Correct 241 ms 101308 KB Output is correct
5 Correct 239 ms 101320 KB Output is correct
6 Correct 222 ms 101264 KB Output is correct
7 Correct 244 ms 101272 KB Output is correct
8 Correct 298 ms 101272 KB Output is correct
9 Correct 226 ms 101388 KB Output is correct
10 Correct 421 ms 101264 KB Output is correct
11 Correct 272 ms 101368 KB Output is correct
12 Correct 353 ms 101324 KB Output is correct
13 Correct 255 ms 101364 KB Output is correct
14 Correct 4 ms 2388 KB Output is correct
15 Correct 237 ms 101268 KB Output is correct
16 Correct 254 ms 101368 KB Output is correct
17 Correct 208 ms 101328 KB Output is correct
18 Correct 201 ms 101324 KB Output is correct
19 Correct 250 ms 101364 KB Output is correct
20 Correct 368 ms 101324 KB Output is correct
21 Correct 442 ms 101488 KB Output is correct
22 Correct 698 ms 101308 KB Output is correct
23 Correct 265 ms 101332 KB Output is correct
24 Correct 403 ms 101320 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2388 KB Output is correct
2 Correct 262 ms 101372 KB Output is correct
3 Correct 253 ms 101332 KB Output is correct
4 Correct 241 ms 101308 KB Output is correct
5 Correct 239 ms 101320 KB Output is correct
6 Correct 222 ms 101264 KB Output is correct
7 Correct 244 ms 101272 KB Output is correct
8 Correct 298 ms 101272 KB Output is correct
9 Correct 226 ms 101388 KB Output is correct
10 Correct 421 ms 101264 KB Output is correct
11 Correct 272 ms 101368 KB Output is correct
12 Correct 353 ms 101324 KB Output is correct
13 Correct 255 ms 101364 KB Output is correct
14 Correct 4 ms 2388 KB Output is correct
15 Correct 237 ms 101268 KB Output is correct
16 Correct 254 ms 101368 KB Output is correct
17 Correct 208 ms 101328 KB Output is correct
18 Correct 201 ms 101324 KB Output is correct
19 Correct 250 ms 101364 KB Output is correct
20 Correct 368 ms 101324 KB Output is correct
21 Correct 442 ms 101488 KB Output is correct
22 Correct 698 ms 101308 KB Output is correct
23 Correct 265 ms 101332 KB Output is correct
24 Correct 403 ms 101320 KB Output is correct
25 Correct 201 ms 100496 KB Output is correct
26 Correct 236 ms 101372 KB Output is correct
27 Correct 229 ms 101368 KB Output is correct
28 Correct 209 ms 101308 KB Output is correct
29 Correct 243 ms 101308 KB Output is correct
30 Correct 266 ms 101484 KB Output is correct
31 Correct 363 ms 101308 KB Output is correct
32 Correct 454 ms 101320 KB Output is correct
33 Correct 637 ms 101252 KB Output is correct
34 Correct 806 ms 101324 KB Output is correct
35 Correct 1248 ms 101376 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2388 KB Output is correct
2 Correct 1717 ms 802716 KB Output is correct
3 Correct 1520 ms 809592 KB Output is correct
4 Correct 1542 ms 811168 KB Output is correct
5 Correct 1543 ms 811164 KB Output is correct
6 Correct 1953 ms 809516 KB Output is correct
7 Correct 2193 ms 807884 KB Output is correct
8 Correct 2 ms 2388 KB Output is correct
9 Correct 262 ms 101372 KB Output is correct
10 Correct 253 ms 101332 KB Output is correct
11 Correct 241 ms 101308 KB Output is correct
12 Correct 239 ms 101320 KB Output is correct
13 Correct 222 ms 101264 KB Output is correct
14 Correct 244 ms 101272 KB Output is correct
15 Correct 298 ms 101272 KB Output is correct
16 Correct 226 ms 101388 KB Output is correct
17 Correct 421 ms 101264 KB Output is correct
18 Correct 272 ms 101368 KB Output is correct
19 Correct 353 ms 101324 KB Output is correct
20 Correct 255 ms 101364 KB Output is correct
21 Correct 4 ms 2388 KB Output is correct
22 Correct 237 ms 101268 KB Output is correct
23 Correct 254 ms 101368 KB Output is correct
24 Correct 208 ms 101328 KB Output is correct
25 Correct 201 ms 101324 KB Output is correct
26 Correct 250 ms 101364 KB Output is correct
27 Correct 368 ms 101324 KB Output is correct
28 Correct 442 ms 101488 KB Output is correct
29 Correct 698 ms 101308 KB Output is correct
30 Correct 265 ms 101332 KB Output is correct
31 Correct 403 ms 101320 KB Output is correct
32 Correct 201 ms 100496 KB Output is correct
33 Correct 236 ms 101372 KB Output is correct
34 Correct 229 ms 101368 KB Output is correct
35 Correct 209 ms 101308 KB Output is correct
36 Correct 243 ms 101308 KB Output is correct
37 Correct 266 ms 101484 KB Output is correct
38 Correct 363 ms 101308 KB Output is correct
39 Correct 454 ms 101320 KB Output is correct
40 Correct 637 ms 101252 KB Output is correct
41 Correct 806 ms 101324 KB Output is correct
42 Correct 1248 ms 101376 KB Output is correct
43 Correct 1 ms 340 KB Output is correct
44 Correct 2 ms 2388 KB Output is correct
45 Correct 1647 ms 814316 KB Output is correct
46 Correct 1549 ms 809756 KB Output is correct
47 Correct 1651 ms 810024 KB Output is correct
48 Correct 1689 ms 812212 KB Output is correct
49 Correct 1878 ms 814364 KB Output is correct
50 Correct 1729 ms 811924 KB Output is correct
51 Correct 1656 ms 812192 KB Output is correct
52 Correct 1765 ms 810016 KB Output is correct
53 Correct 2426 ms 810768 KB Output is correct
54 Correct 2507 ms 811792 KB Output is correct
55 Correct 3296 ms 810884 KB Output is correct
56 Correct 3888 ms 811440 KB Output is correct
57 Correct 2930 ms 811668 KB Output is correct
58 Correct 3005 ms 811552 KB Output is correct
59 Correct 2742 ms 811704 KB Output is correct
60 Correct 3961 ms 811016 KB Output is correct
61 Correct 3876 ms 810912 KB Output is correct