oj.uz

답안 #819273

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
819273 2023-08-10T08:46:57 Z LittleCube 던전 (IOI21_dungeons) C++17
100 / 100
 4337 ms 1988472 KB 
#include "dungeons.h"
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

namespace
{

	struct node
	{
		// value, >= m wil accidently big win (just like mango)
		ll v, m;
	};

	node merge(node l, node r)
	{
		auto [lv, lm] = l;
		auto [rv, rm] = r;
		return node{lv + rv, min(lm, rm - lv)};
	}

	const int C = 10'000'000, P = 25, B = 6, mxL = 10;
	pair<int, vector<int>> calc()
	{
		vector<int> v;
		int b = 1;
		for (; b < C; b *= B)
			v.emplace_back(b);
		v.emplace_back(b);

		return make_pair(v.size(), v);
	}
	int n, m, L;
	int id[mxL][400001][P];
	node go[mxL][400001][P];
	vector<int> s, p, w, l, base;
}

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;
	tie(L, base) = calc();
	cerr << L << '\n';
	for (int t = 0; t < L; t++)
	{
		for (int i = 0; i < n; i++)
			if (s[i] <= base[t])
				go[t][i][0] = node{s[i], (ll)1e18}, id[t][i][0] = w[i];
			else
				go[t][i][0] = node{p[i], s[i]}, id[t][i][0] = l[i];
		go[t][n][0] = node{0, 0}, id[t][n][0] = n;
		for (int k = 0; k + 1 < P; k++)
			for (int i = 0; i <= n; i++)
				go[t][i][k + 1] = merge(go[t][i][k], go[t][id[t][i][k]][k]), id[t][i][k + 1] = id[t][id[t][i][k]][k];
	}
	return;
}

ll simulate(int x, int _z)
{
	ll z = _z;
	int c = upper_bound(base.begin(), base.end(), _z) - base.begin() - 1;

	for (int k = P - 1; k >= 0; k--)
		if (go[c][x][k].m > z)
			z += go[c][x][k].v, x = id[c][x][k];
	if (x == n)
		return z;
	z += s[x];
	x = w[x];
	return simulate(x, z);
}

Compilation message

dungeons.cpp:36:9: warning: '{anonymous}::m' defined but not used [-Wunused-variable]
   36 |  int n, m, L;
      |         ^

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 6 ms 10388 KB Output is correct
4 Correct 227 ms 248428 KB Output is correct
5 Correct 6 ms 10380 KB Output is correct
6 Correct 207 ms 248324 KB Output is correct

Subtask #2
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5460 KB Output is correct
2 Correct 3530 ms 1978240 KB Output is correct
3 Correct 2749 ms 1983732 KB Output is correct
4 Correct 2685 ms 1985236 KB Output is correct
5 Correct 2733 ms 1985220 KB Output is correct
6 Correct 2901 ms 1983612 KB Output is correct
7 Correct 2649 ms 1981960 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5460 KB Output is correct
2 Correct 299 ms 249804 KB Output is correct
3 Correct 298 ms 249984 KB Output is correct
4 Correct 274 ms 249356 KB Output is correct
5 Correct 295 ms 249208 KB Output is correct
6 Correct 338 ms 249488 KB Output is correct
7 Correct 327 ms 249472 KB Output is correct
8 Correct 288 ms 249160 KB Output is correct
9 Correct 289 ms 249232 KB Output is correct
10 Correct 382 ms 249068 KB Output is correct
11 Correct 345 ms 249368 KB Output is correct
12 Correct 478 ms 249596 KB Output is correct
13 Correct 304 ms 249420 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5460 KB Output is correct
2 Correct 299 ms 249804 KB Output is correct
3 Correct 298 ms 249984 KB Output is correct
4 Correct 274 ms 249356 KB Output is correct
5 Correct 295 ms 249208 KB Output is correct
6 Correct 338 ms 249488 KB Output is correct
7 Correct 327 ms 249472 KB Output is correct
8 Correct 288 ms 249160 KB Output is correct
9 Correct 289 ms 249232 KB Output is correct
10 Correct 382 ms 249068 KB Output is correct
11 Correct 345 ms 249368 KB Output is correct
12 Correct 478 ms 249596 KB Output is correct
13 Correct 304 ms 249420 KB Output is correct
14 Correct 3 ms 5460 KB Output is correct
15 Correct 339 ms 249684 KB Output is correct
16 Correct 305 ms 249756 KB Output is correct
17 Correct 263 ms 249432 KB Output is correct
18 Correct 267 ms 249352 KB Output is correct
19 Correct 314 ms 249420 KB Output is correct
20 Correct 286 ms 249212 KB Output is correct
21 Correct 302 ms 249292 KB Output is correct
22 Correct 288 ms 249288 KB Output is correct
23 Correct 335 ms 249412 KB Output is correct
24 Correct 520 ms 249524 KB Output is correct

Subtask #5
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 5460 KB Output is correct
2 Correct 299 ms 249804 KB Output is correct
3 Correct 298 ms 249984 KB Output is correct
4 Correct 274 ms 249356 KB Output is correct
5 Correct 295 ms 249208 KB Output is correct
6 Correct 338 ms 249488 KB Output is correct
7 Correct 327 ms 249472 KB Output is correct
8 Correct 288 ms 249160 KB Output is correct
9 Correct 289 ms 249232 KB Output is correct
10 Correct 382 ms 249068 KB Output is correct
11 Correct 345 ms 249368 KB Output is correct
12 Correct 478 ms 249596 KB Output is correct
13 Correct 304 ms 249420 KB Output is correct
14 Correct 3 ms 5460 KB Output is correct
15 Correct 339 ms 249684 KB Output is correct
16 Correct 305 ms 249756 KB Output is correct
17 Correct 263 ms 249432 KB Output is correct
18 Correct 267 ms 249352 KB Output is correct
19 Correct 314 ms 249420 KB Output is correct
20 Correct 286 ms 249212 KB Output is correct
21 Correct 302 ms 249292 KB Output is correct
22 Correct 288 ms 249288 KB Output is correct
23 Correct 335 ms 249412 KB Output is correct
24 Correct 520 ms 249524 KB Output is correct
25 Correct 279 ms 248688 KB Output is correct
26 Correct 304 ms 249852 KB Output is correct
27 Correct 264 ms 249232 KB Output is correct
28 Correct 258 ms 249276 KB Output is correct
29 Correct 322 ms 249888 KB Output is correct
30 Correct 308 ms 249484 KB Output is correct
31 Correct 357 ms 249204 KB Output is correct
32 Correct 456 ms 249332 KB Output is correct
33 Correct 715 ms 249292 KB Output is correct
34 Correct 1042 ms 249140 KB Output is correct
35 Correct 510 ms 249316 KB Output is correct

Subtask #6
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5460 KB Output is correct
2 Correct 3530 ms 1978240 KB Output is correct
3 Correct 2749 ms 1983732 KB Output is correct
4 Correct 2685 ms 1985236 KB Output is correct
5 Correct 2733 ms 1985220 KB Output is correct
6 Correct 2901 ms 1983612 KB Output is correct
7 Correct 2649 ms 1981960 KB Output is correct
8 Correct 4 ms 5460 KB Output is correct
9 Correct 299 ms 249804 KB Output is correct
10 Correct 298 ms 249984 KB Output is correct
11 Correct 274 ms 249356 KB Output is correct
12 Correct 295 ms 249208 KB Output is correct
13 Correct 338 ms 249488 KB Output is correct
14 Correct 327 ms 249472 KB Output is correct
15 Correct 288 ms 249160 KB Output is correct
16 Correct 289 ms 249232 KB Output is correct
17 Correct 382 ms 249068 KB Output is correct
18 Correct 345 ms 249368 KB Output is correct
19 Correct 478 ms 249596 KB Output is correct
20 Correct 304 ms 249420 KB Output is correct
21 Correct 3 ms 5460 KB Output is correct
22 Correct 339 ms 249684 KB Output is correct
23 Correct 305 ms 249756 KB Output is correct
24 Correct 263 ms 249432 KB Output is correct
25 Correct 267 ms 249352 KB Output is correct
26 Correct 314 ms 249420 KB Output is correct
27 Correct 286 ms 249212 KB Output is correct
28 Correct 302 ms 249292 KB Output is correct
29 Correct 288 ms 249288 KB Output is correct
30 Correct 335 ms 249412 KB Output is correct
31 Correct 520 ms 249524 KB Output is correct
32 Correct 279 ms 248688 KB Output is correct
33 Correct 304 ms 249852 KB Output is correct
34 Correct 264 ms 249232 KB Output is correct
35 Correct 258 ms 249276 KB Output is correct
36 Correct 322 ms 249888 KB Output is correct
37 Correct 308 ms 249484 KB Output is correct
38 Correct 357 ms 249204 KB Output is correct
39 Correct 456 ms 249332 KB Output is correct
40 Correct 715 ms 249292 KB Output is correct
41 Correct 1042 ms 249140 KB Output is correct
42 Correct 510 ms 249316 KB Output is correct
43 Correct 1 ms 468 KB Output is correct
44 Correct 4 ms 5460 KB Output is correct
45 Correct 3126 ms 1988472 KB Output is correct
46 Correct 2752 ms 1983852 KB Output is correct
47 Correct 2707 ms 1984240 KB Output is correct
48 Correct 2626 ms 1986408 KB Output is correct
49 Correct 3010 ms 1988472 KB Output is correct
50 Correct 2926 ms 1986032 KB Output is correct
51 Correct 2819 ms 1986360 KB Output is correct
52 Correct 2819 ms 1984112 KB Output is correct
53 Correct 3832 ms 1984876 KB Output is correct
54 Correct 3357 ms 1985984 KB Output is correct
55 Correct 4337 ms 1985048 KB Output is correct
56 Correct 3448 ms 1985608 KB Output is correct
57 Correct 3388 ms 1985776 KB Output is correct
58 Correct 3640 ms 1985772 KB Output is correct
59 Correct 3678 ms 1985860 KB Output is correct
60 Correct 4172 ms 1985132 KB Output is correct
61 Correct 3866 ms 1985020 KB Output is correct