oj.uz

Submission #616037

# Submission time Handle Problem Language Result Execution time Memory
616037 2022-07-31T18:38:26 Z Clan328 Dungeons Game (IOI21_dungeons) C++17
36 / 100
 7000 ms 107768 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int n;
vector<pair<ll, ll>> G, W;
vl dp;

const int LOG = 25;
vector<vvi> up;
vector<vvl> sum;
vi diffS;

ll getDP(int i) {
	if (dp[i] != -1) return dp[i];
	if (i == n) {
		dp[i] = 0;
		return 0;
	}
	dp[i] = W[i].first+getDP(G[i].first);
	return dp[i];
}

pll dist(int x, int d, int j) {
	ll strength = 0;
	for (int i = LOG-1; i >= 0; i--) {
		if ((d>>i)&1) {
			strength += sum[j][x][i];
			x = up[j][x][i];
		}
	}

	return {x, strength};
}

void init(int nx, vi s, vi p, vi w, vi l) {
	n = nx;
	G = vector<pll>(n);
	W = vector<pll>(n);

	for (int i = 0; i < n; i++) {
		G[i] = {w[i], l[i]};
		W[i] = {s[i], p[i]};
	}

	set<int> tmp;
	for (int i = 0; i < n; i++) tmp.insert(s[i]);

	for (auto it = tmp.begin(); it != tmp.end(); it++) {
		diffS.push_back(*it);
	}

	if (diffS.size() > 5) return;

	dp = vl(n+1, -1);
	for (int i = 0; i <= n; i++) {
		dp[i] = getDP(i);
	}

	up = vector<vvi>(diffS.size(), vvi(n+1, vi(LOG)));
	sum = vector<vvl>(diffS.size(), vvl(n+1, vl(LOG)));
	
	ll curr = 0;
	for (int j = 0; j < diffS.size(); j++) {
		up[j][n][0] = n;
		sum[j][n][0] = 0;
		for (int i = 0; i < n; i++) {
			if (W[i].first <= curr) {
				up[j][i][0] = G[i].first;
				sum[j][i][0] = W[i].first;
			} else {
				up[j][i][0] = G[i].second;
				sum[j][i][0] = W[i].second;
			}
		}

		for (int i = 1; i < LOG; i++) {
			for (int v = 0; v <= n; v++) {
				sum[j][v][i] = sum[j][v][i-1] + sum[j][up[j][v][i-1]][i-1];
				up[j][v][i] = up[j][up[j][v][i-1]][i-1];
			}
		}

		curr = diffS[j];
	}
}

ll simulate(int x, int z) {
	if (diffS.size() > 5) {
		int n = G.size();
		ll strength = z;
		for (int i = x; i != n; ) {
			if (strength >= W[i].first) {
				strength += W[i].first;
				i = G[i].first;
			} else {
				strength += W[i].second;
				i = G[i].second;
			}
		}

		return strength;
	}

	if (z >= diffS[diffS.size()-1]) {
		return z + dp[x];
	}

	int start = 0;
	for (int i = 0; i < diffS.size(); i++) {
		if (z >= diffS[i]) start = i+1;
	}

	ll strength = z;
	int res;
	for (int i = start; i < diffS.size(); i++) {
		int lo = 0, hi = 2e7, mid;
		res = 2e7;
		while (lo <= hi) {
			mid = (lo+hi)/2;
			if (dist(x, mid, i).second+strength >= diffS[i]) {
				res = mid;
				hi = mid -1;
			} else
				lo = mid + 1;
		}

		strength += dist(x, res, i).second;
		x = dist(x, res, i).first;
	}
	
	return strength+dp[x];
}

Compilation message

dungeons.cpp: In function 'void init(int, vi, vi, vi, vi)':
dungeons.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for (int j = 0; j < diffS.size(); j++) {
      |                  ~~^~~~~~~~~~~~~~
dungeons.cpp: In function 'll simulate(int, int)':
dungeons.cpp:118:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |  for (int i = 0; i < diffS.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~
dungeons.cpp:124:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |  for (int i = start; i < diffS.size(); i++) {
      |                      ~~^~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 440 KB Output is correct
4 Correct 24 ms 5040 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 21 ms 4920 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Execution timed out 7041 ms 32972 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 852 KB Output is correct
2 Correct 123 ms 33920 KB Output is correct
3 Correct 109 ms 35016 KB Output is correct
4 Correct 85 ms 35408 KB Output is correct
5 Correct 73 ms 35008 KB Output is correct
6 Correct 201 ms 34064 KB Output is correct
7 Correct 167 ms 33848 KB Output is correct
8 Correct 86 ms 35596 KB Output is correct
9 Correct 98 ms 33968 KB Output is correct
10 Correct 81 ms 35460 KB Output is correct
11 Correct 170 ms 33848 KB Output is correct
12 Correct 729 ms 33848 KB Output is correct
13 Correct 653 ms 33968 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 852 KB Output is correct
2 Correct 123 ms 33920 KB Output is correct
3 Correct 109 ms 35016 KB Output is correct
4 Correct 85 ms 35408 KB Output is correct
5 Correct 73 ms 35008 KB Output is correct
6 Correct 201 ms 34064 KB Output is correct
7 Correct 167 ms 33848 KB Output is correct
8 Correct 86 ms 35596 KB Output is correct
9 Correct 98 ms 33968 KB Output is correct
10 Correct 81 ms 35460 KB Output is correct
11 Correct 170 ms 33848 KB Output is correct
12 Correct 729 ms 33848 KB Output is correct
13 Correct 653 ms 33968 KB Output is correct
14 Correct 4 ms 2004 KB Output is correct
15 Correct 234 ms 71132 KB Output is correct
16 Correct 327 ms 89128 KB Output is correct
17 Correct 303 ms 107696 KB Output is correct
18 Correct 419 ms 107768 KB Output is correct
19 Correct 755 ms 107148 KB Output is correct
20 Correct 546 ms 71976 KB Output is correct
21 Correct 565 ms 89948 KB Output is correct
22 Correct 463 ms 53384 KB Output is correct
23 Correct 757 ms 89180 KB Output is correct
24 Correct 1116 ms 70940 KB Output is correct

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 852 KB Output is correct
2 Correct 123 ms 33920 KB Output is correct
3 Correct 109 ms 35016 KB Output is correct
4 Correct 85 ms 35408 KB Output is correct
5 Correct 73 ms 35008 KB Output is correct
6 Correct 201 ms 34064 KB Output is correct
7 Correct 167 ms 33848 KB Output is correct
8 Correct 86 ms 35596 KB Output is correct
9 Correct 98 ms 33968 KB Output is correct
10 Correct 81 ms 35460 KB Output is correct
11 Correct 170 ms 33848 KB Output is correct
12 Correct 729 ms 33848 KB Output is correct
13 Correct 653 ms 33968 KB Output is correct
14 Correct 4 ms 2004 KB Output is correct
15 Correct 234 ms 71132 KB Output is correct
16 Correct 327 ms 89128 KB Output is correct
17 Correct 303 ms 107696 KB Output is correct
18 Correct 419 ms 107768 KB Output is correct
19 Correct 755 ms 107148 KB Output is correct
20 Correct 546 ms 71976 KB Output is correct
21 Correct 565 ms 89948 KB Output is correct
22 Correct 463 ms 53384 KB Output is correct
23 Correct 757 ms 89180 KB Output is correct
24 Correct 1116 ms 70940 KB Output is correct
25 Correct 33 ms 7508 KB Output is correct
26 Correct 57 ms 8484 KB Output is correct
27 Correct 48 ms 5204 KB Output is correct
28 Correct 371 ms 5300 KB Output is correct
29 Correct 60 ms 8404 KB Output is correct
30 Execution timed out 7052 ms 5452 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Execution timed out 7041 ms 32972 KB Time limit exceeded
3 Halted 0 ms 0 KB -