oj.uz

답안 #835694

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
835694 2023-08-23T17:39:58 Z ttamx 던전 (IOI21_dungeons) C++17
100 / 100
 3442 ms 1932740 KB 
#include "dungeons.h"
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
const int N=400005;
const int K=25;
const int L=8;
const ll inf=1e18;
const int S=1e7;
 
int n;
int s[N],p[N],w[N],l[N];
ll add[N];
 
struct edge{
	int to;
	ll add,lim;
	edge(){}
	edge(int to,ll add,ll lim):to(to),add(add),lim(lim){}
}dp[L][N][K];

void init(int _n,vector<int> _s,vector<int> _p,vector<int> _w,vector<int> _l){
	n=_n;
	for(int i=0;i<n;i++)s[i]=_s[i],p[i]=_p[i],w[i]=_w[i],l[i]=_l[i];
	s[n]=p[n]=0;
	w[n]=l[n]=n;
	vector<vector<int>> adj(n+1);
	for(int i=0;i<n;i++)adj[w[i]].emplace_back(i);
	queue<int> q;
	q.emplace(n);
	while(!q.empty()){
		auto u=q.front();
		q.pop();
		for(auto v:adj[u]){
			add[v]=add[u]+s[v];
			q.emplace(v);
		}
	}
	for(int i=0;i<L;i++){
		for(int u=0;u<n;u++){
			if(s[u]<=(1<<(3*i))){
				dp[i][u][0]=edge(w[u],s[u],inf);
			}else{
				dp[i][u][0]=edge(l[u],p[u],s[u]);
			}
		}
		dp[i][n][0]=edge(n,0,inf);
		for(int j=1;j<K;j++){
			for(int u=0;u<=n;u++){
				int v=dp[i][u][j-1].to;
				dp[i][u][j].to=dp[i][v][j-1].to;
				dp[i][u][j].add=dp[i][u][j-1].add+dp[i][v][j-1].add;
				dp[i][u][j].lim=min(dp[i][u][j-1].lim,dp[i][v][j-1].lim-dp[i][u][j-1].add);
			}
		}
	}
}
 
ll simulate(int x, int z){
	int phase=0;
	ll sz=1;
	int cur=x;
	ll val=z;
	while(cur!=n&&val<S){
		while(sz*8<=val){
			sz*=8;
			phase++;
		}
		for(int i=K-1;i>=0;i--){
			auto e=dp[phase][cur][i];
			if(val>=e.lim)continue;
			val+=e.add;
			cur=e.to;
		}
		if(val>=s[cur]){
			val+=s[cur];
			cur=w[cur];
		}else{
			val+=p[cur];
			cur=l[cur];
		}
	}
	return val+add[cur];
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 6 ms 9960 KB Output is correct
4 Correct 197 ms 239884 KB Output is correct
5 Correct 6 ms 9908 KB Output is correct
6 Correct 184 ms 240108 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5212 KB Output is correct
2 Correct 2375 ms 1920484 KB Output is correct
3 Correct 2251 ms 1923516 KB Output is correct
4 Correct 2226 ms 1923612 KB Output is correct
5 Correct 2160 ms 1917924 KB Output is correct
6 Correct 2343 ms 1920372 KB Output is correct
7 Correct 2160 ms 1923576 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 219 ms 240736 KB Output is correct
3 Correct 230 ms 241084 KB Output is correct
4 Correct 194 ms 242636 KB Output is correct
5 Correct 193 ms 241996 KB Output is correct
6 Correct 228 ms 241964 KB Output is correct
7 Correct 216 ms 241944 KB Output is correct
8 Correct 198 ms 242508 KB Output is correct
9 Correct 207 ms 241704 KB Output is correct
10 Correct 199 ms 242252 KB Output is correct
11 Correct 218 ms 242192 KB Output is correct
12 Correct 303 ms 242252 KB Output is correct
13 Correct 270 ms 241560 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 219 ms 240736 KB Output is correct
3 Correct 230 ms 241084 KB Output is correct
4 Correct 194 ms 242636 KB Output is correct
5 Correct 193 ms 241996 KB Output is correct
6 Correct 228 ms 241964 KB Output is correct
7 Correct 216 ms 241944 KB Output is correct
8 Correct 198 ms 242508 KB Output is correct
9 Correct 207 ms 241704 KB Output is correct
10 Correct 199 ms 242252 KB Output is correct
11 Correct 218 ms 242192 KB Output is correct
12 Correct 303 ms 242252 KB Output is correct
13 Correct 270 ms 241560 KB Output is correct
14 Correct 3 ms 5228 KB Output is correct
15 Correct 220 ms 242148 KB Output is correct
16 Correct 213 ms 242244 KB Output is correct
17 Correct 200 ms 241996 KB Output is correct
18 Correct 207 ms 242096 KB Output is correct
19 Correct 217 ms 241956 KB Output is correct
20 Correct 220 ms 242056 KB Output is correct
21 Correct 224 ms 242196 KB Output is correct
22 Correct 217 ms 242124 KB Output is correct
23 Correct 224 ms 242276 KB Output is correct
24 Correct 360 ms 242084 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 219 ms 240736 KB Output is correct
3 Correct 230 ms 241084 KB Output is correct
4 Correct 194 ms 242636 KB Output is correct
5 Correct 193 ms 241996 KB Output is correct
6 Correct 228 ms 241964 KB Output is correct
7 Correct 216 ms 241944 KB Output is correct
8 Correct 198 ms 242508 KB Output is correct
9 Correct 207 ms 241704 KB Output is correct
10 Correct 199 ms 242252 KB Output is correct
11 Correct 218 ms 242192 KB Output is correct
12 Correct 303 ms 242252 KB Output is correct
13 Correct 270 ms 241560 KB Output is correct
14 Correct 3 ms 5228 KB Output is correct
15 Correct 220 ms 242148 KB Output is correct
16 Correct 213 ms 242244 KB Output is correct
17 Correct 200 ms 241996 KB Output is correct
18 Correct 207 ms 242096 KB Output is correct
19 Correct 217 ms 241956 KB Output is correct
20 Correct 220 ms 242056 KB Output is correct
21 Correct 224 ms 242196 KB Output is correct
22 Correct 217 ms 242124 KB Output is correct
23 Correct 224 ms 242276 KB Output is correct
24 Correct 360 ms 242084 KB Output is correct
25 Correct 183 ms 241356 KB Output is correct
26 Correct 229 ms 242468 KB Output is correct
27 Correct 204 ms 241728 KB Output is correct
28 Correct 204 ms 241712 KB Output is correct
29 Correct 226 ms 242240 KB Output is correct
30 Correct 240 ms 242724 KB Output is correct
31 Correct 240 ms 242504 KB Output is correct
32 Correct 293 ms 242024 KB Output is correct
33 Correct 398 ms 242640 KB Output is correct
34 Correct 814 ms 242540 KB Output is correct
35 Correct 330 ms 242016 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5212 KB Output is correct
2 Correct 2375 ms 1920484 KB Output is correct
3 Correct 2251 ms 1923516 KB Output is correct
4 Correct 2226 ms 1923612 KB Output is correct
5 Correct 2160 ms 1917924 KB Output is correct
6 Correct 2343 ms 1920372 KB Output is correct
7 Correct 2160 ms 1923576 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 219 ms 240736 KB Output is correct
10 Correct 230 ms 241084 KB Output is correct
11 Correct 194 ms 242636 KB Output is correct
12 Correct 193 ms 241996 KB Output is correct
13 Correct 228 ms 241964 KB Output is correct
14 Correct 216 ms 241944 KB Output is correct
15 Correct 198 ms 242508 KB Output is correct
16 Correct 207 ms 241704 KB Output is correct
17 Correct 199 ms 242252 KB Output is correct
18 Correct 218 ms 242192 KB Output is correct
19 Correct 303 ms 242252 KB Output is correct
20 Correct 270 ms 241560 KB Output is correct
21 Correct 3 ms 5228 KB Output is correct
22 Correct 220 ms 242148 KB Output is correct
23 Correct 213 ms 242244 KB Output is correct
24 Correct 200 ms 241996 KB Output is correct
25 Correct 207 ms 242096 KB Output is correct
26 Correct 217 ms 241956 KB Output is correct
27 Correct 220 ms 242056 KB Output is correct
28 Correct 224 ms 242196 KB Output is correct
29 Correct 217 ms 242124 KB Output is correct
30 Correct 224 ms 242276 KB Output is correct
31 Correct 360 ms 242084 KB Output is correct
32 Correct 183 ms 241356 KB Output is correct
33 Correct 229 ms 242468 KB Output is correct
34 Correct 204 ms 241728 KB Output is correct
35 Correct 204 ms 241712 KB Output is correct
36 Correct 226 ms 242240 KB Output is correct
37 Correct 240 ms 242724 KB Output is correct
38 Correct 240 ms 242504 KB Output is correct
39 Correct 293 ms 242024 KB Output is correct
40 Correct 398 ms 242640 KB Output is correct
41 Correct 814 ms 242540 KB Output is correct
42 Correct 330 ms 242016 KB Output is correct
43 Correct 1 ms 340 KB Output is correct
44 Correct 3 ms 5204 KB Output is correct
45 Correct 2231 ms 1929556 KB Output is correct
46 Correct 2087 ms 1924956 KB Output is correct
47 Correct 2157 ms 1925328 KB Output is correct
48 Correct 2077 ms 1930064 KB Output is correct
49 Correct 2288 ms 1929540 KB Output is correct
50 Correct 2393 ms 1929704 KB Output is correct
51 Correct 2163 ms 1929492 KB Output is correct
52 Correct 2409 ms 1927776 KB Output is correct
53 Correct 2736 ms 1927440 KB Output is correct
54 Correct 2811 ms 1932740 KB Output is correct
55 Correct 3442 ms 1931796 KB Output is correct
56 Correct 3077 ms 1928356 KB Output is correct
57 Correct 2919 ms 1928404 KB Output is correct
58 Correct 2682 ms 1928288 KB Output is correct
59 Correct 2701 ms 1928576 KB Output is correct
60 Correct 3141 ms 1930080 KB Output is correct
61 Correct 3029 ms 1931684 KB Output is correct