oj.uz

답안 #488518

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
488518 2021-11-19T12:36:18 Z 8e7 던전 (IOI21_dungeons) C++17
100 / 100
 2560 ms 1014524 KB 
//Challenge: Accepted
#include "dungeons.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <assert.h>
using namespace std;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 400005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int n;
vector<int> s, p, w, l;
struct WIN{
	int anc[19][maxn];
	ll ma[19][maxn];
	ll sum[19][maxn];
	void build() {
		for (int i = 0;i < n;i++) {
			anc[0][i] = w[i];
			ma[0][i] = s[i];
			sum[0][i] = s[i];
		}
		anc[0][n] = n;
		for (int i = 1;i < 19;i++) {
			for (int j = 0;j <= n;j++) {
				anc[i][j] = anc[i-1][anc[i-1][j]];
				sum[i][j] = sum[i-1][j] + sum[i-1][anc[i-1][j]];
				ma[i][j] = max(ma[i-1][j], ma[i-1][anc[i-1][j]] - sum[i-1][j]);
			}
		}
	}
	void move(int &x, ll &val) { //brings it to the nearest loss
		for (int i = 18;i >= 0;i--) {
			if (val >= ma[i][x]) {
				val += sum[i][x];
				x = anc[i][x];
			}
		}
	}
} win;
const int inf = 1<<26;
struct LOSE{
	int anc[15][maxn];
	int mi[15][maxn];
	int sum[15][maxn];
	void build(int bit) {
		for (int i = 0;i < n;i++) {
			if (s[i] >= (1<<bit)) mi[0][i] = s[i];
			else mi[0][i] = 1<<(bit+2);
			if (s[i] < (1<<bit)) sum[0][i] = s[i], anc[0][i] = w[i];
			else sum[0][i] = p[i], anc[0][i] = l[i];
		}
		anc[0][n] = n;
		for (int i = 1;i < 15;i++) {
			for (int j = 0;j <= n;j++) {
				anc[i][j] = anc[i-1][anc[i-1][anc[i-1][j]]];
				sum[i][j] = min(inf, sum[i-1][j] + sum[i-1][anc[i-1][j]] + sum[i-1][anc[i-1][anc[i-1][j]]]);
				mi[i][j] = max(0, min(mi[i-1][j], min(mi[i-1][anc[i-1][j]] - sum[i-1][j], mi[i-1][anc[i-1][anc[i-1][j]]] - sum[i-1][j] - sum[i-1][anc[i-1][j]])));
			}
		}
	}
	void move(int &x, ll &val) { //brings it to the nearest win
		for (int i = 14;i >= 0;i--) {
			if (val < mi[i][x]) {
				val += sum[i][x];
				x = anc[i][x];
			}
			if (val < mi[i][x]) {
				val += sum[i][x];
				x = anc[i][x];
			}
		}
	}
} lose[12];
void init(int nv, vector<int> sv, vector<int> pv, vector<int> wv, vector<int> lv) {
	n = nv;
	s = sv, p = pv, w = wv, l = lv;	
	win.build();	
	for (int i = 0;i < 12;i++) lose[i].build(i*2);
}
 
long long simulate(int x, int z) {
	ll ans = z;
	for (int i = 0;i < 12 && x != n;i++) {
		if (ans >= (1<<(2*i+2))) continue; 
		for (int j = 0;j < 4;j++) {
			lose[i].move(x, ans);
			if (x != n && ans >= s[x]) {
				ans += s[x];
				x = w[x];
			}
			if (ans >= (1<<(2*i+2))) {
				break;
			}
		}
	}
	win.move(x, ans);
	return ans;
}
/*
3 2
2 6 9
3 1 2
2 2 3
1 0 1
0 1
2 3
 
3 3
14 14 14
2 1 1 
1 2 3
1 2 0
0 0
2 4
1 1
*/

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4428 KB Output is correct
2 Correct 2 ms 4556 KB Output is correct
3 Correct 6 ms 9548 KB Output is correct
4 Correct 125 ms 130916 KB Output is correct
5 Correct 6 ms 9548 KB Output is correct
6 Correct 127 ms 130872 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6988 KB Output is correct
2 Correct 963 ms 1014524 KB Output is correct
3 Correct 938 ms 1014176 KB Output is correct
4 Correct 1012 ms 1014204 KB Output is correct
5 Correct 985 ms 1014152 KB Output is correct
6 Correct 1567 ms 1014060 KB Output is correct
7 Correct 1399 ms 1014084 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6988 KB Output is correct
2 Correct 172 ms 131840 KB Output is correct
3 Correct 149 ms 131792 KB Output is correct
4 Correct 166 ms 131712 KB Output is correct
5 Correct 159 ms 131788 KB Output is correct
6 Correct 218 ms 131784 KB Output is correct
7 Correct 224 ms 131848 KB Output is correct
8 Correct 321 ms 131844 KB Output is correct
9 Correct 162 ms 131772 KB Output is correct
10 Correct 302 ms 131792 KB Output is correct
11 Correct 196 ms 131708 KB Output is correct
12 Correct 263 ms 131848 KB Output is correct
13 Correct 198 ms 131836 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6988 KB Output is correct
2 Correct 172 ms 131840 KB Output is correct
3 Correct 149 ms 131792 KB Output is correct
4 Correct 166 ms 131712 KB Output is correct
5 Correct 159 ms 131788 KB Output is correct
6 Correct 218 ms 131784 KB Output is correct
7 Correct 224 ms 131848 KB Output is correct
8 Correct 321 ms 131844 KB Output is correct
9 Correct 162 ms 131772 KB Output is correct
10 Correct 302 ms 131792 KB Output is correct
11 Correct 196 ms 131708 KB Output is correct
12 Correct 263 ms 131848 KB Output is correct
13 Correct 198 ms 131836 KB Output is correct
14 Correct 4 ms 6988 KB Output is correct
15 Correct 157 ms 131760 KB Output is correct
16 Correct 196 ms 131824 KB Output is correct
17 Correct 191 ms 131748 KB Output is correct
18 Correct 185 ms 131756 KB Output is correct
19 Correct 224 ms 131764 KB Output is correct
20 Correct 299 ms 131780 KB Output is correct
21 Correct 356 ms 131732 KB Output is correct
22 Correct 452 ms 131700 KB Output is correct
23 Correct 224 ms 131816 KB Output is correct
24 Correct 597 ms 131732 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6988 KB Output is correct
2 Correct 172 ms 131840 KB Output is correct
3 Correct 149 ms 131792 KB Output is correct
4 Correct 166 ms 131712 KB Output is correct
5 Correct 159 ms 131788 KB Output is correct
6 Correct 218 ms 131784 KB Output is correct
7 Correct 224 ms 131848 KB Output is correct
8 Correct 321 ms 131844 KB Output is correct
9 Correct 162 ms 131772 KB Output is correct
10 Correct 302 ms 131792 KB Output is correct
11 Correct 196 ms 131708 KB Output is correct
12 Correct 263 ms 131848 KB Output is correct
13 Correct 198 ms 131836 KB Output is correct
14 Correct 4 ms 6988 KB Output is correct
15 Correct 157 ms 131760 KB Output is correct
16 Correct 196 ms 131824 KB Output is correct
17 Correct 191 ms 131748 KB Output is correct
18 Correct 185 ms 131756 KB Output is correct
19 Correct 224 ms 131764 KB Output is correct
20 Correct 299 ms 131780 KB Output is correct
21 Correct 356 ms 131732 KB Output is correct
22 Correct 452 ms 131700 KB Output is correct
23 Correct 224 ms 131816 KB Output is correct
24 Correct 597 ms 131732 KB Output is correct
25 Correct 133 ms 131016 KB Output is correct
26 Correct 185 ms 131796 KB Output is correct
27 Correct 166 ms 131752 KB Output is correct
28 Correct 165 ms 131776 KB Output is correct
29 Correct 226 ms 131840 KB Output is correct
30 Correct 319 ms 131796 KB Output is correct
31 Correct 370 ms 131780 KB Output is correct
32 Correct 556 ms 131852 KB Output is correct
33 Correct 409 ms 131796 KB Output is correct
34 Correct 956 ms 131696 KB Output is correct
35 Correct 645 ms 131776 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 6988 KB Output is correct
2 Correct 963 ms 1014524 KB Output is correct
3 Correct 938 ms 1014176 KB Output is correct
4 Correct 1012 ms 1014204 KB Output is correct
5 Correct 985 ms 1014152 KB Output is correct
6 Correct 1567 ms 1014060 KB Output is correct
7 Correct 1399 ms 1014084 KB Output is correct
8 Correct 4 ms 6988 KB Output is correct
9 Correct 172 ms 131840 KB Output is correct
10 Correct 149 ms 131792 KB Output is correct
11 Correct 166 ms 131712 KB Output is correct
12 Correct 159 ms 131788 KB Output is correct
13 Correct 218 ms 131784 KB Output is correct
14 Correct 224 ms 131848 KB Output is correct
15 Correct 321 ms 131844 KB Output is correct
16 Correct 162 ms 131772 KB Output is correct
17 Correct 302 ms 131792 KB Output is correct
18 Correct 196 ms 131708 KB Output is correct
19 Correct 263 ms 131848 KB Output is correct
20 Correct 198 ms 131836 KB Output is correct
21 Correct 4 ms 6988 KB Output is correct
22 Correct 157 ms 131760 KB Output is correct
23 Correct 196 ms 131824 KB Output is correct
24 Correct 191 ms 131748 KB Output is correct
25 Correct 185 ms 131756 KB Output is correct
26 Correct 224 ms 131764 KB Output is correct
27 Correct 299 ms 131780 KB Output is correct
28 Correct 356 ms 131732 KB Output is correct
29 Correct 452 ms 131700 KB Output is correct
30 Correct 224 ms 131816 KB Output is correct
31 Correct 597 ms 131732 KB Output is correct
32 Correct 133 ms 131016 KB Output is correct
33 Correct 185 ms 131796 KB Output is correct
34 Correct 166 ms 131752 KB Output is correct
35 Correct 165 ms 131776 KB Output is correct
36 Correct 226 ms 131840 KB Output is correct
37 Correct 319 ms 131796 KB Output is correct
38 Correct 370 ms 131780 KB Output is correct
39 Correct 556 ms 131852 KB Output is correct
40 Correct 409 ms 131796 KB Output is correct
41 Correct 956 ms 131696 KB Output is correct
42 Correct 645 ms 131776 KB Output is correct
43 Correct 2 ms 4428 KB Output is correct
44 Correct 5 ms 6988 KB Output is correct
45 Correct 1354 ms 1014056 KB Output is correct
46 Correct 1101 ms 1013956 KB Output is correct
47 Correct 1077 ms 1013988 KB Output is correct
48 Correct 993 ms 1014064 KB Output is correct
49 Correct 1348 ms 1014176 KB Output is correct
50 Correct 1214 ms 1014004 KB Output is correct
51 Correct 941 ms 1014084 KB Output is correct
52 Correct 1303 ms 1013948 KB Output is correct
53 Correct 2322 ms 1013916 KB Output is correct
54 Correct 1324 ms 1013936 KB Output is correct
55 Correct 1918 ms 1014072 KB Output is correct
56 Correct 2300 ms 1014064 KB Output is correct
57 Correct 2222 ms 1014164 KB Output is correct
58 Correct 2560 ms 1013928 KB Output is correct
59 Correct 2391 ms 1014060 KB Output is correct
60 Correct 1898 ms 1014324 KB Output is correct
61 Correct 1596 ms 1014180 KB Output is correct