oj.uz

답안 #609379

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
609379 2022-07-27T14:36:18 Z FatihSolak 던전 (IOI21_dungeons) C++17
62 / 100
 7000 ms 303580 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
#define N 400005
#define M 50005
#define K 30
#define X 10
using namespace std;
struct node{
	int to;
	long long val;
};
struct node2{
	int to;
	long long sum;
	long long maxi;
};
node sp[M][X][K];
node2 sp2[N][K];
vector<int> numbers;
int sz;
int n;
bool subtask4 = 0;
bool subtask2 = 1;
vector<int> s,p,w,l;
void init(int n_, vector<int> s_, vector<int> p_, vector<int> w_, vector<int> l_) {
	n = n_;
	s = s_;
	p = p_;
	w = w_;
	l = l_;
	for(int i = 0;i<n;i++){
		subtask2 &= (s[i] == p[i]);
		numbers.push_back(s[i]);
	}
	sort(numbers.begin(),numbers.end());
	numbers.resize(unique(numbers.begin(),numbers.end())-numbers.begin());
	sz = numbers.size();
	if(sz <= 5 && n <= 50000)subtask4 = 1;
	if(subtask4){
		for(int x = 0;x<=sz;x++){
			sp[n][x][0].to = n;
			sp[n][x][0].val = 0;
			for(int i = 0;i<n;i++){
				int num = upper_bound(numbers.begin(),numbers.end(),s[i]) - numbers.begin();
				if(num <= x){
					sp[i][x][0].to = w[i];
					sp[i][x][0].val = s[i];
				}
				else{
					sp[i][x][0].to = l[i];
					sp[i][x][0].val = p[i];
				}
			}
			for(int j = 1;j<K;j++){
				for(int i = 0;i<=n;i++){
					sp[i][x][j].val = sp[i][x][j-1].val + sp[sp[i][x][j-1].to][x][j-1].val;
					sp[i][x][j].to = sp[sp[i][x][j-1].to][x][j-1].to;
				}
			}
		}
	}
	if(subtask2){
		for(int i = 0;i<n;i++){
			sp2[i][0].to = w[i];
			sp2[i][0].sum = s[i];
			sp2[i][0].maxi = s[i];
		}
		sp2[n][0].to = n;
		sp2[n][0].sum = 0;
		sp2[n][0].maxi = 0;
		for(int j = 1;j<K;j++){
			for(int i = 0;i<=n;i++){
				sp2[i][j].to = sp2[sp2[i][j-1].to][j-1].to;
				sp2[i][j].sum = sp2[i][j-1].sum + sp2[sp2[i][j-1].to][j-1].sum;
				sp2[i][j].maxi = max(sp2[i][j-1].maxi,sp2[sp2[i][j-1].to][j-1].maxi - sp2[i][j-1].sum);
			}
		}
	}
	return;
}

long long simulate(int x, int z) {
	long long pw = z;
	int now = upper_bound(numbers.begin(),numbers.end(),pw) - numbers.begin();
	if(subtask2){
		while(x != n){
			for(int i = K-1;i>=0;i--){
				if(sp2[x][i].maxi <= pw){
					pw += sp2[x][i].sum;
					x = sp2[x][i].to;
				}
			}
			if(x != n){
				pw += p[x];
				x = l[x];
			}
		}	
		return pw;
	}
	if(subtask4){
		while(x != n){
			//cout << now << " " << x << " " << pw << endl;
			if(now == sz){
				pw += sp[x][now][K-1].val;
				x = sp[x][now][K-1].to;
				assert(x == n);
			}
			else{
				for(int i = K-1;i>=0;i--){
					if(sp[x][now][i].val + pw < numbers[now]){
						pw += sp[x][now][i].val;
						x = sp[x][now][i].to;
					}
				}
				pw += sp[x][now][0].val;
				x = sp[x][now][0].to;
				while(now != sz && pw >= numbers[now])
					now++;
			}
		}
		return pw;
	}
	while(x != n){
		if(s[x] <= pw){
			pw += s[x];
			x = w[x];
		}
		else{
			pw += p[x];
			x = l[x];
		}
	}
	return pw;
}

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 20 ms 3020 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 20 ms 3024 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 980 KB Output is correct
2 Correct 494 ms 303268 KB Output is correct
3 Correct 459 ms 303396 KB Output is correct
4 Correct 523 ms 303380 KB Output is correct
5 Correct 449 ms 303292 KB Output is correct
6 Correct 509 ms 303388 KB Output is correct
7 Correct 533 ms 303580 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 170 ms 238548 KB Output is correct
3 Correct 174 ms 238532 KB Output is correct
4 Correct 159 ms 238556 KB Output is correct
5 Correct 154 ms 238524 KB Output is correct
6 Correct 168 ms 238532 KB Output is correct
7 Correct 183 ms 238584 KB Output is correct
8 Correct 168 ms 238532 KB Output is correct
9 Correct 181 ms 238508 KB Output is correct
10 Correct 155 ms 238540 KB Output is correct
11 Correct 167 ms 238500 KB Output is correct
12 Correct 249 ms 238484 KB Output is correct
13 Correct 234 ms 238612 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 170 ms 238548 KB Output is correct
3 Correct 174 ms 238532 KB Output is correct
4 Correct 159 ms 238556 KB Output is correct
5 Correct 154 ms 238524 KB Output is correct
6 Correct 168 ms 238532 KB Output is correct
7 Correct 183 ms 238584 KB Output is correct
8 Correct 168 ms 238532 KB Output is correct
9 Correct 181 ms 238508 KB Output is correct
10 Correct 155 ms 238540 KB Output is correct
11 Correct 167 ms 238500 KB Output is correct
12 Correct 249 ms 238484 KB Output is correct
13 Correct 234 ms 238612 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 211 ms 238536 KB Output is correct
16 Correct 230 ms 238568 KB Output is correct
17 Correct 241 ms 238584 KB Output is correct
18 Correct 275 ms 238536 KB Output is correct
19 Correct 284 ms 238604 KB Output is correct
20 Correct 256 ms 238604 KB Output is correct
21 Correct 256 ms 238664 KB Output is correct
22 Correct 199 ms 238584 KB Output is correct
23 Correct 271 ms 238576 KB Output is correct
24 Correct 319 ms 238600 KB Output is correct

Subtask #5
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 170 ms 238548 KB Output is correct
3 Correct 174 ms 238532 KB Output is correct
4 Correct 159 ms 238556 KB Output is correct
5 Correct 154 ms 238524 KB Output is correct
6 Correct 168 ms 238532 KB Output is correct
7 Correct 183 ms 238584 KB Output is correct
8 Correct 168 ms 238532 KB Output is correct
9 Correct 181 ms 238508 KB Output is correct
10 Correct 155 ms 238540 KB Output is correct
11 Correct 167 ms 238500 KB Output is correct
12 Correct 249 ms 238484 KB Output is correct
13 Correct 234 ms 238612 KB Output is correct
14 Correct 3 ms 5076 KB Output is correct
15 Correct 211 ms 238536 KB Output is correct
16 Correct 230 ms 238568 KB Output is correct
17 Correct 241 ms 238584 KB Output is correct
18 Correct 275 ms 238536 KB Output is correct
19 Correct 284 ms 238604 KB Output is correct
20 Correct 256 ms 238604 KB Output is correct
21 Correct 256 ms 238664 KB Output is correct
22 Correct 199 ms 238584 KB Output is correct
23 Correct 271 ms 238576 KB Output is correct
24 Correct 319 ms 238600 KB Output is correct
25 Correct 22 ms 3028 KB Output is correct
26 Correct 50 ms 3796 KB Output is correct
27 Correct 49 ms 3796 KB Output is correct
28 Correct 328 ms 3812 KB Output is correct
29 Correct 45 ms 3796 KB Output is correct
30 Execution timed out 7015 ms 3792 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 980 KB Output is correct
2 Correct 494 ms 303268 KB Output is correct
3 Correct 459 ms 303396 KB Output is correct
4 Correct 523 ms 303380 KB Output is correct
5 Correct 449 ms 303292 KB Output is correct
6 Correct 509 ms 303388 KB Output is correct
7 Correct 533 ms 303580 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 170 ms 238548 KB Output is correct
10 Correct 174 ms 238532 KB Output is correct
11 Correct 159 ms 238556 KB Output is correct
12 Correct 154 ms 238524 KB Output is correct
13 Correct 168 ms 238532 KB Output is correct
14 Correct 183 ms 238584 KB Output is correct
15 Correct 168 ms 238532 KB Output is correct
16 Correct 181 ms 238508 KB Output is correct
17 Correct 155 ms 238540 KB Output is correct
18 Correct 167 ms 238500 KB Output is correct
19 Correct 249 ms 238484 KB Output is correct
20 Correct 234 ms 238612 KB Output is correct
21 Correct 3 ms 5076 KB Output is correct
22 Correct 211 ms 238536 KB Output is correct
23 Correct 230 ms 238568 KB Output is correct
24 Correct 241 ms 238584 KB Output is correct
25 Correct 275 ms 238536 KB Output is correct
26 Correct 284 ms 238604 KB Output is correct
27 Correct 256 ms 238604 KB Output is correct
28 Correct 256 ms 238664 KB Output is correct
29 Correct 199 ms 238584 KB Output is correct
30 Correct 271 ms 238576 KB Output is correct
31 Correct 319 ms 238600 KB Output is correct
32 Correct 22 ms 3028 KB Output is correct
33 Correct 50 ms 3796 KB Output is correct
34 Correct 49 ms 3796 KB Output is correct
35 Correct 328 ms 3812 KB Output is correct
36 Correct 45 ms 3796 KB Output is correct
37 Execution timed out 7015 ms 3792 KB Time limit exceeded
38 Halted 0 ms 0 KB -