Submission #526017

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
526017	2022-02-13T14:09:02 Z	LucaDantas	Dungeons Game (IOI21_dungeons)	C++17	100 / 100	5404 ms	1828868 KB

dungeons

#include "dungeons.h"
#include <vector>

constexpr int maxn = 4e5+10, logn = 24, log_lift = 12, base_lift = 4;
constexpr int inf = 0x3f3f3f3f;

struct FunctionalGraph {
	int f[log_lift][maxn];
	int tab[log_lift][maxn];
	long long cost[log_lift][maxn];

	void add_i(const int& i, const int& x, const int& v, const int& st) { f[0][i] = x, cost[0][i] = v, tab[0][i] = st; }

	void build(int n) {
		f[0][n] = n;

		for(int l = 1; l < log_lift; l++) {
			for(int i = 0; i <= n; i++) {
				f[l][i] = i;
				tab[l][i] = tab[l-1][i];

				for(int k = 0; k < base_lift; k++) {
					if(tab[l-1][f[l][i]] < inf)
						tab[l][i] = std::max(0ll, std::min((long long)tab[l][i], tab[l-1][f[l][i]] - cost[l][i]));
					cost[l][i] += cost[l-1][f[l][i]];
					f[l][i] = f[l-1][f[l][i]];
				}
			}
		}
	}

	void go(int& x, long long& val) {
		for(int l = log_lift-1; l >= 0; l--)
			for(int k = 0; k < base_lift-1; k++)
				if(tab[l][x] >  val || tab[l][x] == inf) val += cost[l][x], x = f[l][x];
	}
} graph[logn];

void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
	for(int lg = 0; lg < logn; lg++) {
		for(int i = 0; i < n; i++) {
			if(s[i] < (2<<lg)) graph[lg].add_i(i, w[i], s[i], inf);
			else graph[lg].add_i(i, l[i], p[i], s[i]);
		}
		graph[lg].build(n);
	}

	return;
}

long long simulate(int x, int z) {
	long long val = z;
	for(int lg = 0; lg < logn; lg++)
		graph[lg].go(x, val);
	return val;
}

Subtask #1
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	6604 KB	Output is correct
2	Correct	4 ms	6604 KB	Output is correct
3	Correct	15 ms	15692 KB	Output is correct
4	Correct	287 ms	234472 KB	Output is correct
5	Correct	14 ms	15692 KB	Output is correct
6	Correct	296 ms	234208 KB	Output is correct

Subtask #2
26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	11228 KB	Output is correct
2	Correct	1904 ms	1824036 KB	Output is correct
3	Correct	1805 ms	1823960 KB	Output is correct
4	Correct	2053 ms	1825604 KB	Output is correct
5	Correct	2534 ms	1825516 KB	Output is correct
6	Correct	1883 ms	1824072 KB	Output is correct
7	Correct	1882 ms	1822360 KB	Output is correct

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	11232 KB	Output is correct
2	Correct	675 ms	235820 KB	Output is correct
3	Correct	687 ms	236044 KB	Output is correct
4	Correct	342 ms	235428 KB	Output is correct
5	Correct	358 ms	235188 KB	Output is correct
6	Correct	583 ms	235432 KB	Output is correct
7	Correct	544 ms	235468 KB	Output is correct
8	Correct	376 ms	235128 KB	Output is correct
9	Correct	394 ms	235180 KB	Output is correct
10	Correct	318 ms	235116 KB	Output is correct
11	Correct	445 ms	235384 KB	Output is correct
12	Correct	873 ms	235588 KB	Output is correct
13	Correct	734 ms	235416 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	11232 KB	Output is correct
2	Correct	675 ms	235820 KB	Output is correct
3	Correct	687 ms	236044 KB	Output is correct
4	Correct	342 ms	235428 KB	Output is correct
5	Correct	358 ms	235188 KB	Output is correct
6	Correct	583 ms	235432 KB	Output is correct
7	Correct	544 ms	235468 KB	Output is correct
8	Correct	376 ms	235128 KB	Output is correct
9	Correct	394 ms	235180 KB	Output is correct
10	Correct	318 ms	235116 KB	Output is correct
11	Correct	445 ms	235384 KB	Output is correct
12	Correct	873 ms	235588 KB	Output is correct
13	Correct	734 ms	235416 KB	Output is correct
14	Correct	10 ms	11212 KB	Output is correct
15	Correct	548 ms	235616 KB	Output is correct
16	Correct	708 ms	235868 KB	Output is correct
17	Correct	456 ms	235316 KB	Output is correct
18	Correct	488 ms	235480 KB	Output is correct
19	Correct	550 ms	235460 KB	Output is correct
20	Correct	447 ms	235204 KB	Output is correct
21	Correct	470 ms	235332 KB	Output is correct
22	Correct	380 ms	235332 KB	Output is correct
23	Correct	476 ms	235556 KB	Output is correct
24	Correct	880 ms	235472 KB	Output is correct

Subtask #5
27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	11232 KB	Output is correct
2	Correct	675 ms	235820 KB	Output is correct
3	Correct	687 ms	236044 KB	Output is correct
4	Correct	342 ms	235428 KB	Output is correct
5	Correct	358 ms	235188 KB	Output is correct
6	Correct	583 ms	235432 KB	Output is correct
7	Correct	544 ms	235468 KB	Output is correct
8	Correct	376 ms	235128 KB	Output is correct
9	Correct	394 ms	235180 KB	Output is correct
10	Correct	318 ms	235116 KB	Output is correct
11	Correct	445 ms	235384 KB	Output is correct
12	Correct	873 ms	235588 KB	Output is correct
13	Correct	734 ms	235416 KB	Output is correct
14	Correct	10 ms	11212 KB	Output is correct
15	Correct	548 ms	235616 KB	Output is correct
16	Correct	708 ms	235868 KB	Output is correct
17	Correct	456 ms	235316 KB	Output is correct
18	Correct	488 ms	235480 KB	Output is correct
19	Correct	550 ms	235460 KB	Output is correct
20	Correct	447 ms	235204 KB	Output is correct
21	Correct	470 ms	235332 KB	Output is correct
22	Correct	380 ms	235332 KB	Output is correct
23	Correct	476 ms	235556 KB	Output is correct
24	Correct	880 ms	235472 KB	Output is correct
25	Correct	325 ms	234692 KB	Output is correct
26	Correct	715 ms	235848 KB	Output is correct
27	Correct	480 ms	235332 KB	Output is correct
28	Correct	421 ms	235312 KB	Output is correct
29	Correct	724 ms	235688 KB	Output is correct
30	Correct	400 ms	235576 KB	Output is correct
31	Correct	418 ms	235104 KB	Output is correct
32	Correct	709 ms	235312 KB	Output is correct
33	Correct	692 ms	235372 KB	Output is correct
34	Correct	915 ms	235132 KB	Output is correct
35	Correct	775 ms	235380 KB	Output is correct

Subtask #6
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	11228 KB	Output is correct
2	Correct	1904 ms	1824036 KB	Output is correct
3	Correct	1805 ms	1823960 KB	Output is correct
4	Correct	2053 ms	1825604 KB	Output is correct
5	Correct	2534 ms	1825516 KB	Output is correct
6	Correct	1883 ms	1824072 KB	Output is correct
7	Correct	1882 ms	1822360 KB	Output is correct
8	Correct	11 ms	11232 KB	Output is correct
9	Correct	675 ms	235820 KB	Output is correct
10	Correct	687 ms	236044 KB	Output is correct
11	Correct	342 ms	235428 KB	Output is correct
12	Correct	358 ms	235188 KB	Output is correct
13	Correct	583 ms	235432 KB	Output is correct
14	Correct	544 ms	235468 KB	Output is correct
15	Correct	376 ms	235128 KB	Output is correct
16	Correct	394 ms	235180 KB	Output is correct
17	Correct	318 ms	235116 KB	Output is correct
18	Correct	445 ms	235384 KB	Output is correct
19	Correct	873 ms	235588 KB	Output is correct
20	Correct	734 ms	235416 KB	Output is correct
21	Correct	10 ms	11212 KB	Output is correct
22	Correct	548 ms	235616 KB	Output is correct
23	Correct	708 ms	235868 KB	Output is correct
24	Correct	456 ms	235316 KB	Output is correct
25	Correct	488 ms	235480 KB	Output is correct
26	Correct	550 ms	235460 KB	Output is correct
27	Correct	447 ms	235204 KB	Output is correct
28	Correct	470 ms	235332 KB	Output is correct
29	Correct	380 ms	235332 KB	Output is correct
30	Correct	476 ms	235556 KB	Output is correct
31	Correct	880 ms	235472 KB	Output is correct
32	Correct	325 ms	234692 KB	Output is correct
33	Correct	715 ms	235848 KB	Output is correct
34	Correct	480 ms	235332 KB	Output is correct
35	Correct	421 ms	235312 KB	Output is correct
36	Correct	724 ms	235688 KB	Output is correct
37	Correct	400 ms	235576 KB	Output is correct
38	Correct	418 ms	235104 KB	Output is correct
39	Correct	709 ms	235312 KB	Output is correct
40	Correct	692 ms	235372 KB	Output is correct
41	Correct	915 ms	235132 KB	Output is correct
42	Correct	775 ms	235380 KB	Output is correct
43	Correct	3 ms	6572 KB	Output is correct
44	Correct	11 ms	11184 KB	Output is correct
45	Correct	4014 ms	1828780 KB	Output is correct
46	Correct	2519 ms	1824348 KB	Output is correct
47	Correct	2587 ms	1824480 KB	Output is correct
48	Correct	2666 ms	1826672 KB	Output is correct
49	Correct	4048 ms	1828868 KB	Output is correct
50	Correct	1860 ms	1826300 KB	Output is correct
51	Correct	2338 ms	1826772 KB	Output is correct
52	Correct	1852 ms	1824520 KB	Output is correct
53	Correct	5404 ms	1823104 KB	Output is correct
54	Correct	2732 ms	1821956 KB	Output is correct
55	Correct	2787 ms	1821692 KB	Output is correct
56	Correct	4749 ms	1821052 KB	Output is correct
57	Correct	4768 ms	1820296 KB	Output is correct
58	Correct	4800 ms	1819396 KB	Output is correct
59	Correct	4910 ms	1818512 KB	Output is correct
60	Correct	4954 ms	1817916 KB	Output is correct
61	Correct	3513 ms	1817092 KB	Output is correct

Submission #526017

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 26.0 / 26.0

Subtask #3 13.0 / 13.0

Subtask #4 12.0 / 12.0

Subtask #5 27.0 / 27.0

Subtask #6 11.0 / 11.0

Subtask #1
11.0 / 11.0

Subtask #2
26.0 / 26.0

Subtask #3
13.0 / 13.0

Subtask #4
12.0 / 12.0

Subtask #5
27.0 / 27.0

Subtask #6
11.0 / 11.0