oj.uz

Submission #446850

# Submission time Handle Problem Language Result Execution time Memory
446850 2021-07-23T13:56:05 Z prvocislo Dungeons Game (IOI21_dungeons) C++17
100 / 100
 3882 ms 1566672 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int maxd1 = 8, maxd2 = 24, maxn = 4e5 + 5, base = 8;
const ll inf = 1e18 + 5ll;
vector<pair<int, int> > g[maxn];
int kam[maxd1][maxd2][maxn], pw[maxd1+1], n;
vector<int> s, p, w, l;
ll sum[maxd1][maxd2][maxn], mini[maxd1][maxd2][maxn], onlywin[maxn];
void dfs(int u, ll w)
{
	onlywin[u] = w;
	for (pair<int, int> i : g[u]) dfs(i.first, w+i.second);
}
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) 
{
	s.push_back(0), p.push_back(0), w.push_back(n), l.push_back(n);
	::n = n, ::s = s, ::p = p, ::w = w, ::l = l;
	pw[0] = 1;
	for (int i = 1; i <= maxd1; i++) pw[i] = pw[i-1] * base;
	for (int i = 0; i < maxd1; i++)
	{
		for (int j = 0; j <= n; j++)
		{
			if (s[j] <= pw[i]) 
			{
				sum[i][0][j] = s[j], kam[i][0][j] = w[j];
				mini[i][0][j] = inf;
			}
			else 
			{
				sum[i][0][j] = p[j], kam[i][0][j] = l[j];
				mini[i][0][j] = s[j];
			}
		}
		for (int j = 1; j < maxd2; j++) for (int k = 0; k < maxn; k++)
		{
			kam[i][j][k] = kam[i][j-1][kam[i][j-1][k]];
			sum[i][j][k] = sum[i][j-1][k] + sum[i][j-1][kam[i][j-1][k]];
			mini[i][j][k] = min(mini[i][j-1][k], mini[i][j-1][kam[i][j-1][k]] - sum[i][j-1][k]);
		}
	}
	for (int i = 0; i < n; i++) g[w[i]].push_back({i, s[i]});
	dfs(n, 0);
}
ll simulate(int x, int z) 
{
	ll st = z;
	for (int i = 0; i < maxd1; i++)
	{
		while (x != n && st < pw[i+1])
		{
			for (int j = maxd2-1; j >= 0; j--) if (mini[i][j][x] > st)
			{
				st += sum[i][j][x];
				x = kam[i][j][x];
			}
			st += s[x];
			x = w[x];
		}	
	}
	return st + onlywin[x];
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 882 ms 1450176 KB Output is correct
2 Correct 866 ms 1450216 KB Output is correct
3 Correct 838 ms 1450792 KB Output is correct
4 Correct 879 ms 1461764 KB Output is correct
5 Correct 889 ms 1450708 KB Output is correct
6 Correct 893 ms 1461744 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 857 ms 1450488 KB Output is correct
2 Correct 1199 ms 1558588 KB Output is correct
3 Correct 1190 ms 1565216 KB Output is correct
4 Correct 1186 ms 1566672 KB Output is correct
5 Correct 1385 ms 1551720 KB Output is correct
6 Correct 1330 ms 1558692 KB Output is correct
7 Correct 1281 ms 1563388 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 855 ms 1450484 KB Output is correct
2 Correct 1097 ms 1464360 KB Output is correct
3 Correct 948 ms 1465380 KB Output is correct
4 Correct 904 ms 1465564 KB Output is correct
5 Correct 908 ms 1464628 KB Output is correct
6 Correct 1014 ms 1463788 KB Output is correct
7 Correct 999 ms 1463716 KB Output is correct
8 Correct 980 ms 1465396 KB Output is correct
9 Correct 967 ms 1463576 KB Output is correct
10 Correct 912 ms 1465448 KB Output is correct
11 Correct 995 ms 1463768 KB Output is correct
12 Correct 1054 ms 1463908 KB Output is correct
13 Correct 952 ms 1463468 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 855 ms 1450484 KB Output is correct
2 Correct 1097 ms 1464360 KB Output is correct
3 Correct 948 ms 1465380 KB Output is correct
4 Correct 904 ms 1465564 KB Output is correct
5 Correct 908 ms 1464628 KB Output is correct
6 Correct 1014 ms 1463788 KB Output is correct
7 Correct 999 ms 1463716 KB Output is correct
8 Correct 980 ms 1465396 KB Output is correct
9 Correct 967 ms 1463576 KB Output is correct
10 Correct 912 ms 1465448 KB Output is correct
11 Correct 995 ms 1463768 KB Output is correct
12 Correct 1054 ms 1463908 KB Output is correct
13 Correct 952 ms 1463468 KB Output is correct
14 Correct 866 ms 1450588 KB Output is correct
15 Correct 925 ms 1463984 KB Output is correct
16 Correct 989 ms 1464352 KB Output is correct
17 Correct 929 ms 1464476 KB Output is correct
18 Correct 926 ms 1464696 KB Output is correct
19 Correct 1000 ms 1463832 KB Output is correct
20 Correct 970 ms 1464656 KB Output is correct
21 Correct 984 ms 1464812 KB Output is correct
22 Correct 947 ms 1464256 KB Output is correct
23 Correct 955 ms 1463780 KB Output is correct
24 Correct 1100 ms 1463876 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 855 ms 1450484 KB Output is correct
2 Correct 1097 ms 1464360 KB Output is correct
3 Correct 948 ms 1465380 KB Output is correct
4 Correct 904 ms 1465564 KB Output is correct
5 Correct 908 ms 1464628 KB Output is correct
6 Correct 1014 ms 1463788 KB Output is correct
7 Correct 999 ms 1463716 KB Output is correct
8 Correct 980 ms 1465396 KB Output is correct
9 Correct 967 ms 1463576 KB Output is correct
10 Correct 912 ms 1465448 KB Output is correct
11 Correct 995 ms 1463768 KB Output is correct
12 Correct 1054 ms 1463908 KB Output is correct
13 Correct 952 ms 1463468 KB Output is correct
14 Correct 866 ms 1450588 KB Output is correct
15 Correct 925 ms 1463984 KB Output is correct
16 Correct 989 ms 1464352 KB Output is correct
17 Correct 929 ms 1464476 KB Output is correct
18 Correct 926 ms 1464696 KB Output is correct
19 Correct 1000 ms 1463832 KB Output is correct
20 Correct 970 ms 1464656 KB Output is correct
21 Correct 984 ms 1464812 KB Output is correct
22 Correct 947 ms 1464256 KB Output is correct
23 Correct 955 ms 1463780 KB Output is correct
24 Correct 1100 ms 1463876 KB Output is correct
25 Correct 892 ms 1463108 KB Output is correct
26 Correct 945 ms 1464216 KB Output is correct
27 Correct 928 ms 1463624 KB Output is correct
28 Correct 952 ms 1463640 KB Output is correct
29 Correct 979 ms 1464056 KB Output is correct
30 Correct 993 ms 1465812 KB Output is correct
31 Correct 992 ms 1465532 KB Output is correct
32 Correct 1138 ms 1463760 KB Output is correct
33 Correct 1613 ms 1464524 KB Output is correct
34 Correct 2115 ms 1464244 KB Output is correct
35 Correct 1513 ms 1463728 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 857 ms 1450488 KB Output is correct
2 Correct 1199 ms 1558588 KB Output is correct
3 Correct 1190 ms 1565216 KB Output is correct
4 Correct 1186 ms 1566672 KB Output is correct
5 Correct 1385 ms 1551720 KB Output is correct
6 Correct 1330 ms 1558692 KB Output is correct
7 Correct 1281 ms 1563388 KB Output is correct
8 Correct 855 ms 1450484 KB Output is correct
9 Correct 1097 ms 1464360 KB Output is correct
10 Correct 948 ms 1465380 KB Output is correct
11 Correct 904 ms 1465564 KB Output is correct
12 Correct 908 ms 1464628 KB Output is correct
13 Correct 1014 ms 1463788 KB Output is correct
14 Correct 999 ms 1463716 KB Output is correct
15 Correct 980 ms 1465396 KB Output is correct
16 Correct 967 ms 1463576 KB Output is correct
17 Correct 912 ms 1465448 KB Output is correct
18 Correct 995 ms 1463768 KB Output is correct
19 Correct 1054 ms 1463908 KB Output is correct
20 Correct 952 ms 1463468 KB Output is correct
21 Correct 866 ms 1450588 KB Output is correct
22 Correct 925 ms 1463984 KB Output is correct
23 Correct 989 ms 1464352 KB Output is correct
24 Correct 929 ms 1464476 KB Output is correct
25 Correct 926 ms 1464696 KB Output is correct
26 Correct 1000 ms 1463832 KB Output is correct
27 Correct 970 ms 1464656 KB Output is correct
28 Correct 984 ms 1464812 KB Output is correct
29 Correct 947 ms 1464256 KB Output is correct
30 Correct 955 ms 1463780 KB Output is correct
31 Correct 1100 ms 1463876 KB Output is correct
32 Correct 892 ms 1463108 KB Output is correct
33 Correct 945 ms 1464216 KB Output is correct
34 Correct 928 ms 1463624 KB Output is correct
35 Correct 952 ms 1463640 KB Output is correct
36 Correct 979 ms 1464056 KB Output is correct
37 Correct 993 ms 1465812 KB Output is correct
38 Correct 992 ms 1465532 KB Output is correct
39 Correct 1138 ms 1463760 KB Output is correct
40 Correct 1613 ms 1464524 KB Output is correct
41 Correct 2115 ms 1464244 KB Output is correct
42 Correct 1513 ms 1463728 KB Output is correct
43 Correct 911 ms 1450136 KB Output is correct
44 Correct 885 ms 1450468 KB Output is correct
45 Correct 1995 ms 1554848 KB Output is correct
46 Correct 1589 ms 1550184 KB Output is correct
47 Correct 1478 ms 1550680 KB Output is correct
48 Correct 1248 ms 1561336 KB Output is correct
49 Correct 2085 ms 1554728 KB Output is correct
50 Correct 1254 ms 1560900 KB Output is correct
51 Correct 1223 ms 1559288 KB Output is correct
52 Correct 1275 ms 1558924 KB Output is correct
53 Correct 2918 ms 1551756 KB Output is correct
54 Correct 2212 ms 1557368 KB Output is correct
55 Correct 2656 ms 1556492 KB Output is correct
56 Correct 2959 ms 1552464 KB Output is correct
57 Correct 3882 ms 1552668 KB Output is correct
58 Correct 3207 ms 1552576 KB Output is correct
59 Correct 3344 ms 1552856 KB Output is correct
60 Correct 2533 ms 1555856 KB Output is correct
61 Correct 2347 ms 1556124 KB Output is correct