oj.uz

Submission #984835

# Submission time Handle Problem Language Result Execution time Memory
984835 2024-05-17T06:45:42 Z pavement Escape Route 2 (JOI24_escape2) C++17
23 / 100
 242 ms 25412 KB 
#include <bits/stdc++.h>
using namespace std;

using ii = pair<int, int>;
using ll = long long;

#define mp make_pair
#define pb push_back
#define eb emplace_back

int N, T, Q, _idx, M[100005], anc[25][100005];
ll dep[100005];
vector<int> idx[100005];
vector<ii> V[100005];

ll f(int u, int k) {
	int v = u;
	for (int j = 0; j < 20; j++) {
		if (k & (1 << j)) {
			v = anc[j][v];
		}
	}
	return dep[u] - dep[v];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> T;
	for (int i = 1; i < N; i++) {
		cin >> M[i];
		for (int j = 0, a, b; j < M[i]; j++) {
			cin >> a >> b;
			V[i].eb(a, b);
			idx[i].pb(++_idx);
		}
		sort(V[i].begin(), V[i].end());
		for (int j = (int)V[i].size() - 1, sf = (int)2e9; j >= 0; j--) {
			sf = min(sf, V[i][j].second);
			V[i][j].second = sf;
		}
	}
	for (int i = N - 2; i >= 1; i--) {
		for (int j = 0; j < M[i]; j++) {
			int tmp = lower_bound(V[i + 1].begin(), V[i + 1].end(), mp(V[i][j].second, -1)) - V[i + 1].begin();
			ii potential_to = mp(V[i + 1][0].second + T - V[i][j].second, idx[i + 1][0]);
			if (tmp < (int)V[i + 1].size()) {
				potential_to = min(potential_to, mp(V[i + 1][tmp].second - V[i][j].second, idx[i + 1][tmp]));
			}
			anc[0][idx[i][j]] = potential_to.second;
			for (int k = 1; k <= 20; k++) {
				if (anc[k - 1][idx[i][j]] == 0) {
					break;
				}
				anc[k][idx[i][j]] = anc[k - 1][anc[k - 1][idx[i][j]]];
			}
			dep[idx[i][j]] = dep[potential_to.second] + potential_to.first;
		}
	}
	for (int i = 1; i < N; i++) {
		sort(idx[i].begin(), idx[i].end(), [&](const auto &lhs, const auto &rhs) {
			return V[i][lhs].second < V[i][rhs].second;
		});
		int mn = *min_element(idx[i].begin(), idx[i].end());
		vector<ii> copy_V(V[i].begin(), V[i].end());
		for (int j = 0; j < M[i]; j++) {
			V[i][j] = copy_V[idx[i][j] - mn];
		}
	}
	cin >> Q;
	for (int L, R; Q--; ) {
		cin >> L >> R;
		int lo = 0, hi = M[L] - 1;
		//~ while (hi - lo >= 3) {
			//~ int m1 = lo + (hi - lo) / 3;
			//~ int m2 = hi - (hi - lo) / 3;
			//~ ll f1 = f(idx[L][m1], R - L - 1) + V[L][m1].second - V[L][m1].first;
			//~ ll f2 = f(idx[L][m2], R - L - 1) + V[L][m2].second - V[L][m2].first;
			//~ if (f1 < f2) {
				//~ hi = m2;
			//~ } else {
				//~ lo = m1;
			//~ }
		//~ }
		ll ans = (ll)1e18;
		for (int i = lo; i <= hi; i++) {
			ans = min(ans, f(idx[L][i], R - L - 1) + V[L][i].second - V[L][i].first);
		}
		cout << ans << '\n';
	}
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 51 ms 9644 KB Output is correct
3 Correct 58 ms 13908 KB Output is correct
4 Correct 80 ms 14716 KB Output is correct
5 Correct 62 ms 13924 KB Output is correct
6 Correct 76 ms 14932 KB Output is correct
7 Correct 77 ms 14880 KB Output is correct
8 Correct 58 ms 13900 KB Output is correct
9 Correct 76 ms 14928 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 51 ms 9644 KB Output is correct
3 Correct 58 ms 13908 KB Output is correct
4 Correct 80 ms 14716 KB Output is correct
5 Correct 62 ms 13924 KB Output is correct
6 Correct 76 ms 14932 KB Output is correct
7 Correct 77 ms 14880 KB Output is correct
8 Correct 58 ms 13900 KB Output is correct
9 Correct 76 ms 14928 KB Output is correct
10 Correct 2 ms 6744 KB Output is correct
11 Correct 112 ms 14512 KB Output is correct
12 Correct 118 ms 15708 KB Output is correct
13 Correct 113 ms 14524 KB Output is correct
14 Correct 106 ms 14412 KB Output is correct
15 Correct 95 ms 16212 KB Output is correct
16 Correct 110 ms 10528 KB Output is correct
17 Runtime error 12 ms 21848 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 51 ms 9644 KB Output is correct
3 Correct 58 ms 13908 KB Output is correct
4 Correct 80 ms 14716 KB Output is correct
5 Correct 62 ms 13924 KB Output is correct
6 Correct 76 ms 14932 KB Output is correct
7 Correct 77 ms 14880 KB Output is correct
8 Correct 58 ms 13900 KB Output is correct
9 Correct 76 ms 14928 KB Output is correct
10 Correct 128 ms 21076 KB Output is correct
11 Correct 195 ms 24076 KB Output is correct
12 Correct 193 ms 23896 KB Output is correct
13 Correct 199 ms 22744 KB Output is correct
14 Correct 212 ms 23892 KB Output is correct
15 Correct 242 ms 23992 KB Output is correct
16 Correct 154 ms 21248 KB Output is correct
17 Correct 225 ms 23920 KB Output is correct
18 Correct 78 ms 20052 KB Output is correct
19 Correct 83 ms 19796 KB Output is correct
20 Correct 102 ms 20196 KB Output is correct
21 Correct 81 ms 20152 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 51 ms 9644 KB Output is correct
3 Correct 58 ms 13908 KB Output is correct
4 Correct 80 ms 14716 KB Output is correct
5 Correct 62 ms 13924 KB Output is correct
6 Correct 76 ms 14932 KB Output is correct
7 Correct 77 ms 14880 KB Output is correct
8 Correct 58 ms 13900 KB Output is correct
9 Correct 76 ms 14928 KB Output is correct
10 Correct 2 ms 6744 KB Output is correct
11 Correct 112 ms 14512 KB Output is correct
12 Correct 118 ms 15708 KB Output is correct
13 Correct 113 ms 14524 KB Output is correct
14 Correct 106 ms 14412 KB Output is correct
15 Correct 95 ms 16212 KB Output is correct
16 Correct 110 ms 10528 KB Output is correct
17 Runtime error 12 ms 21848 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Runtime error 33 ms 25412 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 51 ms 9644 KB Output is correct
3 Correct 58 ms 13908 KB Output is correct
4 Correct 80 ms 14716 KB Output is correct
5 Correct 62 ms 13924 KB Output is correct
6 Correct 76 ms 14932 KB Output is correct
7 Correct 77 ms 14880 KB Output is correct
8 Correct 58 ms 13900 KB Output is correct
9 Correct 76 ms 14928 KB Output is correct
10 Correct 2 ms 6744 KB Output is correct
11 Correct 112 ms 14512 KB Output is correct
12 Correct 118 ms 15708 KB Output is correct
13 Correct 113 ms 14524 KB Output is correct
14 Correct 106 ms 14412 KB Output is correct
15 Correct 95 ms 16212 KB Output is correct
16 Correct 110 ms 10528 KB Output is correct
17 Runtime error 12 ms 21848 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -