oj.uz

Submission #817463

# Submission time Handle Problem Language Result Execution time Memory
817463 2023-08-09T12:44:12 Z I_Love_EliskaM_ Dungeons Game (IOI21_dungeons) C++17
50 / 100
 7000 ms 423860 KB 
#include "dungeons.h"
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<n; ++i)
#define pb push_back
#define all(x) x.begin(), x.end()
using ll = long long;
#define pi pair<ll,ll>
#define f first
#define s second

const int N=4e5+55;
const int K=24;
struct up {
	ll v, x, mn;
};
up jump[N][K];
int d[N];

int to[N], x[N], s[N];

const int K2=19;
struct win {
	ll v, x, mx;
};
win go[N][K2];

int n;

void init(int _n, vector<int> _s, vector<int> p, vector<int> w, vector<int> l) {
	n=_n;

	for (int i=n-1; i>=0; --i) {
		d[i]=d[w[i]]+s[i];
	}
	forn(i,n) s[i]=_s[i]; s[n]=0;
	forn(i,n) to[i]=l[i]; to[n]=n;
	forn(i,n) x[i]=p[i]; x[n]=0;
	
	forn(i,n+1) jump[i][0]={to[i],x[i],min(s[i],s[to[i]]-x[i])};

	for (int j=1; j<K; ++j) {
		forn(i,n+1) {

			int u=i;
			auto a = jump[u][j-1];
			int v = a.v;
			auto b = jump[v][j-1];

			jump[i][j] = {b.v, a.x+b.x, min(a.mn, b.mn-a.x)};

		}
	}

	go[n][0] = { n, 0, 0 };
	forn(i,n) go[i][0] = { w[i], s[i], s[i] };

	for (int j=1; j<K2; ++j) {
		forn(i,n+1) {

			int u=i;
			auto a = go[u][j-1];
			int v = a.v;
			auto b = go[v][j-1];

			go[i][j] = { b.v, a.x+b.x, max(a.mx, b.mx-a.x) };

		}
	}

	//for (int j=0; j<3; ++j) {
	//	forn(i,n+1) cout<<i<<' '<<j<<": "<<jump[i][j].v<<' '<<jump[i][j].x<<' '<<jump[i][j].mn<<'\n';
	//}
	//for (int j=0; j<3; ++j) {
	//	forn(i,n+1) cout<<i<<' '<<j<<": "<<go[i][j].v<<' '<<go[i][j].x<<' '<<go[i][j].mx<<'\n';
	//}

}

long long simulate(int x, int z) {

	int u=x;
	ll ans=z;

	while (u<n) {

		for (int j=K-1; j>=0; --j) {
			if (ans >= jump[u][j].mn) continue;
			ans+=jump[u][j].x;
			u=jump[u][j].v;
		}
		if (ans<s[u]) {
			ans+=jump[u][0].x;
			u=jump[u][0].v;
			assert(ans>=s[u]);
		}
		
		for (int j=K2-1; j>=0; --j) {
			if (ans < go[u][j].mx) continue;
			ans += go[u][j].x;
			u = go[u][j].v;
		}

	}

	return ans;

}

Compilation message

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:6:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    6 | #define forn(i,n) for(int i=0; i<n; ++i)
      |                   ^~~
dungeons.cpp:39:2: note: in expansion of macro 'forn'
   39 |  forn(i,n) to[i]=l[i]; to[n]=n;
      |  ^~~~
dungeons.cpp:39:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   39 |  forn(i,n) to[i]=l[i]; to[n]=n;
      |                        ^~
dungeons.cpp:6:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    6 | #define forn(i,n) for(int i=0; i<n; ++i)
      |                   ^~~
dungeons.cpp:40:2: note: in expansion of macro 'forn'
   40 |  forn(i,n) x[i]=p[i]; x[n]=0;
      |  ^~~~
dungeons.cpp:40:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   40 |  forn(i,n) x[i]=p[i]; x[n]=0;
      |                       ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 2388 KB Output is correct
4 Correct 56 ms 53056 KB Output is correct
5 Correct 2 ms 2388 KB Output is correct
6 Correct 53 ms 53060 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 616 ms 423860 KB Output is correct
3 Correct 596 ms 423792 KB Output is correct
4 Correct 606 ms 423792 KB Output is correct
5 Correct 615 ms 423760 KB Output is correct
6 Correct 646 ms 423756 KB Output is correct
7 Correct 588 ms 423744 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1364 KB Output is correct
2 Correct 79 ms 53916 KB Output is correct
3 Correct 79 ms 53956 KB Output is correct
4 Correct 79 ms 53952 KB Output is correct
5 Correct 77 ms 53836 KB Output is correct
6 Correct 79 ms 53924 KB Output is correct
7 Correct 92 ms 53960 KB Output is correct
8 Correct 89 ms 53960 KB Output is correct
9 Correct 79 ms 53928 KB Output is correct
10 Correct 79 ms 53836 KB Output is correct
11 Correct 83 ms 53932 KB Output is correct
12 Correct 167 ms 53940 KB Output is correct
13 Correct 153 ms 55144 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1364 KB Output is correct
2 Correct 79 ms 53916 KB Output is correct
3 Correct 79 ms 53956 KB Output is correct
4 Correct 79 ms 53952 KB Output is correct
5 Correct 77 ms 53836 KB Output is correct
6 Correct 79 ms 53924 KB Output is correct
7 Correct 92 ms 53960 KB Output is correct
8 Correct 89 ms 53960 KB Output is correct
9 Correct 79 ms 53928 KB Output is correct
10 Correct 79 ms 53836 KB Output is correct
11 Correct 83 ms 53932 KB Output is correct
12 Correct 167 ms 53940 KB Output is correct
13 Correct 153 ms 55144 KB Output is correct
14 Correct 3 ms 1340 KB Output is correct
15 Correct 182 ms 55332 KB Output is correct
16 Correct 105 ms 55552 KB Output is correct
17 Correct 91 ms 54984 KB Output is correct
18 Correct 102 ms 55168 KB Output is correct
19 Correct 102 ms 55192 KB Output is correct
20 Correct 130 ms 54952 KB Output is correct
21 Correct 100 ms 55056 KB Output is correct
22 Execution timed out 7021 ms 55092 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1364 KB Output is correct
2 Correct 79 ms 53916 KB Output is correct
3 Correct 79 ms 53956 KB Output is correct
4 Correct 79 ms 53952 KB Output is correct
5 Correct 77 ms 53836 KB Output is correct
6 Correct 79 ms 53924 KB Output is correct
7 Correct 92 ms 53960 KB Output is correct
8 Correct 89 ms 53960 KB Output is correct
9 Correct 79 ms 53928 KB Output is correct
10 Correct 79 ms 53836 KB Output is correct
11 Correct 83 ms 53932 KB Output is correct
12 Correct 167 ms 53940 KB Output is correct
13 Correct 153 ms 55144 KB Output is correct
14 Correct 3 ms 1340 KB Output is correct
15 Correct 182 ms 55332 KB Output is correct
16 Correct 105 ms 55552 KB Output is correct
17 Correct 91 ms 54984 KB Output is correct
18 Correct 102 ms 55168 KB Output is correct
19 Correct 102 ms 55192 KB Output is correct
20 Correct 130 ms 54952 KB Output is correct
21 Correct 100 ms 55056 KB Output is correct
22 Execution timed out 7021 ms 55092 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1364 KB Output is correct
2 Correct 616 ms 423860 KB Output is correct
3 Correct 596 ms 423792 KB Output is correct
4 Correct 606 ms 423792 KB Output is correct
5 Correct 615 ms 423760 KB Output is correct
6 Correct 646 ms 423756 KB Output is correct
7 Correct 588 ms 423744 KB Output is correct
8 Correct 2 ms 1364 KB Output is correct
9 Correct 79 ms 53916 KB Output is correct
10 Correct 79 ms 53956 KB Output is correct
11 Correct 79 ms 53952 KB Output is correct
12 Correct 77 ms 53836 KB Output is correct
13 Correct 79 ms 53924 KB Output is correct
14 Correct 92 ms 53960 KB Output is correct
15 Correct 89 ms 53960 KB Output is correct
16 Correct 79 ms 53928 KB Output is correct
17 Correct 79 ms 53836 KB Output is correct
18 Correct 83 ms 53932 KB Output is correct
19 Correct 167 ms 53940 KB Output is correct
20 Correct 153 ms 55144 KB Output is correct
21 Correct 3 ms 1340 KB Output is correct
22 Correct 182 ms 55332 KB Output is correct
23 Correct 105 ms 55552 KB Output is correct
24 Correct 91 ms 54984 KB Output is correct
25 Correct 102 ms 55168 KB Output is correct
26 Correct 102 ms 55192 KB Output is correct
27 Correct 130 ms 54952 KB Output is correct
28 Correct 100 ms 55056 KB Output is correct
29 Execution timed out 7021 ms 55092 KB Time limit exceeded
30 Halted 0 ms 0 KB -