oj.uz

Submission #721026

# Submission time Handle Problem Language Result Execution time Memory
721026 2023-04-10T08:15:22 Z baojiaopisu Dungeons Game (IOI21_dungeons) C++17
50 / 100
 7000 ms 502164 KB 
#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;

#define fi first
#define se second
#define left BAO
#define right ANH
#define pb push_back
#define pf push_front
#define mp make_pair
#define ins insert
#define btpc __builtin_popcount
#define btclz __builtin_clz

#define sz(x) (int)(x.size());
#define all(x) x.begin(), x.end()
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y)
        {
            x = y;
            return true;
        }
        return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y)
        {
            x = y;
            return true;
        }
        return false;
    }

const int MOD = 1e9 + 7; //998244353

template<class X, class Y>
	void add(X &x, const Y &y) {
		x = (x + y);
		if(x >= MOD) x -= MOD;
	}

template<class X, class Y> 
	void sub(X &x, const Y &y) {
		x = (x - y);
		if(x < 0) x += MOD;
	}

/* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/

const ll INF = 1e9;
const int N = 4e5 + 10;
const int LOG = 24;

struct F {
	int u;
	ll x, tot;
};
F lose[N][LOG + 2], win[N][LOG + 2];
int n;

void init(int N, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
	n = N;
	for(int i = 0; i <= n; i++) {
		for(int j = 0; j <= LOG; j++) {
			lose[i][j].u = win[i][j].u = -1;
		}
	}

	for(int i = 0; i < n; i++) {
		lose[i][0].x = s[i];
		lose[i][0].u = l[i];
		win[i][0].x = s[i];
		win[i][0].u = w[i];
		lose[i][0].tot = p[i];
		win[i][0].tot = s[i];
	}

	for(int j = 1; j <= LOG; j++) {
		for(int i = 0; i < n; i++) {
			int u = win[i][j - 1].u;
			if(u != -1) {
				if(win[u][j - 1].u != -1) {
					win[i][j].u = win[u][j - 1].u;
					win[i][j].x = max(win[i][j - 1].x, win[u][j - 1].x - win[i][j - 1].tot);
					win[i][j].tot = win[i][j - 1].tot + win[u][j - 1].tot;
					maximize(win[i][j].x, 0);
				}
			}

			u = lose[i][j - 1].u;
			if(u != -1) {
				if(lose[u][j - 1].u != -1) {
					lose[i][j].u = lose[u][j - 1].u;
					lose[i][j].x = min(lose[i][j - 1].x, lose[u][j - 1].x - lose[i][j - 1].tot);
					lose[i][j].tot = lose[i][j - 1].tot + lose[u][j - 1].tot;	
					maximize(lose[i][j].x, 0);
				}
			}
		}
	}
}

ll simulate(int pos, int W) {
	ll w = W;
	while(pos < n) {
		for(int i = LOG; i >= 0; i--) {
			if(win[pos][i].u == -1) continue;
			if(w >= win[pos][i].x) {
				w += win[pos][i].tot;
				pos = win[pos][i].u;
			}
		}

		for(int i = LOG; i >= 0; i--) {
			if(lose[pos][i].u == -1) continue;
			if(w < lose[pos][i].x) {
				w += lose[pos][i].tot;
				pos = lose[pos][i].u;
			}
		}
	}

	return w;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 3 ms 2772 KB Output is correct
4 Correct 78 ms 62908 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 69 ms 62856 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 707 ms 502164 KB Output is correct
3 Correct 654 ms 502164 KB Output is correct
4 Correct 646 ms 502024 KB Output is correct
5 Correct 610 ms 502096 KB Output is correct
6 Correct 745 ms 502080 KB Output is correct
7 Correct 647 ms 502088 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 125 ms 63720 KB Output is correct
3 Correct 127 ms 63636 KB Output is correct
4 Correct 107 ms 63732 KB Output is correct
5 Correct 105 ms 63628 KB Output is correct
6 Correct 113 ms 63708 KB Output is correct
7 Correct 125 ms 63720 KB Output is correct
8 Correct 108 ms 63712 KB Output is correct
9 Correct 95 ms 63688 KB Output is correct
10 Correct 117 ms 63716 KB Output is correct
11 Correct 125 ms 63692 KB Output is correct
12 Correct 219 ms 63620 KB Output is correct
13 Correct 162 ms 63716 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 125 ms 63720 KB Output is correct
3 Correct 127 ms 63636 KB Output is correct
4 Correct 107 ms 63732 KB Output is correct
5 Correct 105 ms 63628 KB Output is correct
6 Correct 113 ms 63708 KB Output is correct
7 Correct 125 ms 63720 KB Output is correct
8 Correct 108 ms 63712 KB Output is correct
9 Correct 95 ms 63688 KB Output is correct
10 Correct 117 ms 63716 KB Output is correct
11 Correct 125 ms 63692 KB Output is correct
12 Correct 219 ms 63620 KB Output is correct
13 Correct 162 ms 63716 KB Output is correct
14 Correct 2 ms 1492 KB Output is correct
15 Correct 287 ms 63736 KB Output is correct
16 Correct 113 ms 63720 KB Output is correct
17 Correct 113 ms 63672 KB Output is correct
18 Correct 114 ms 63712 KB Output is correct
19 Correct 115 ms 63692 KB Output is correct
20 Correct 132 ms 63708 KB Output is correct
21 Correct 134 ms 63704 KB Output is correct
22 Execution timed out 7097 ms 63728 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 1492 KB Output is correct
2 Correct 125 ms 63720 KB Output is correct
3 Correct 127 ms 63636 KB Output is correct
4 Correct 107 ms 63732 KB Output is correct
5 Correct 105 ms 63628 KB Output is correct
6 Correct 113 ms 63708 KB Output is correct
7 Correct 125 ms 63720 KB Output is correct
8 Correct 108 ms 63712 KB Output is correct
9 Correct 95 ms 63688 KB Output is correct
10 Correct 117 ms 63716 KB Output is correct
11 Correct 125 ms 63692 KB Output is correct
12 Correct 219 ms 63620 KB Output is correct
13 Correct 162 ms 63716 KB Output is correct
14 Correct 2 ms 1492 KB Output is correct
15 Correct 287 ms 63736 KB Output is correct
16 Correct 113 ms 63720 KB Output is correct
17 Correct 113 ms 63672 KB Output is correct
18 Correct 114 ms 63712 KB Output is correct
19 Correct 115 ms 63692 KB Output is correct
20 Correct 132 ms 63708 KB Output is correct
21 Correct 134 ms 63704 KB Output is correct
22 Execution timed out 7097 ms 63728 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1492 KB Output is correct
2 Correct 707 ms 502164 KB Output is correct
3 Correct 654 ms 502164 KB Output is correct
4 Correct 646 ms 502024 KB Output is correct
5 Correct 610 ms 502096 KB Output is correct
6 Correct 745 ms 502080 KB Output is correct
7 Correct 647 ms 502088 KB Output is correct
8 Correct 2 ms 1492 KB Output is correct
9 Correct 125 ms 63720 KB Output is correct
10 Correct 127 ms 63636 KB Output is correct
11 Correct 107 ms 63732 KB Output is correct
12 Correct 105 ms 63628 KB Output is correct
13 Correct 113 ms 63708 KB Output is correct
14 Correct 125 ms 63720 KB Output is correct
15 Correct 108 ms 63712 KB Output is correct
16 Correct 95 ms 63688 KB Output is correct
17 Correct 117 ms 63716 KB Output is correct
18 Correct 125 ms 63692 KB Output is correct
19 Correct 219 ms 63620 KB Output is correct
20 Correct 162 ms 63716 KB Output is correct
21 Correct 2 ms 1492 KB Output is correct
22 Correct 287 ms 63736 KB Output is correct
23 Correct 113 ms 63720 KB Output is correct
24 Correct 113 ms 63672 KB Output is correct
25 Correct 114 ms 63712 KB Output is correct
26 Correct 115 ms 63692 KB Output is correct
27 Correct 132 ms 63708 KB Output is correct
28 Correct 134 ms 63704 KB Output is correct
29 Execution timed out 7097 ms 63728 KB Time limit exceeded
30 Halted 0 ms 0 KB -