oj.uz

Submission #823816

# Submission time Handle Problem Language Result Execution time Memory
823816 2023-08-13T07:32:56 Z vjudge1 Sky Walking (IOI19_walk) C++17
10 / 100
 4000 ms 351948 KB 
#include<bits/stdc++.h>
#include "walk.h"

using namespace std;
using ll = long long;
int n, m;

const int N = 1e5 + 10;
const int M = 2e6 + 10;
const ll INF = 1e15;

vector<pair<int, ll>> G[M];

vector<int> in[N];
int inx[N];


long long min_distance(vector<int> x, vector<int> h, vector<int> l, vector<int> r, vector<int> y, int s, int g) {
	n = (int)x.size(), m = (int)y.size();
	for(int i = 0; i < m; i++) {
		for(int building = l[i]; building <= r[i]; building++) {
			if(y[i] <= h[building]) in[building].push_back(y[i]);
		}
	}

	for(int i = 0; i < n; i++) {
		in[i].push_back(0);
		sort(in[i].begin(), in[i].end());
		if(i) inx[i] = inx[i - 1] + (int)in[i - 1].size();
		for(int r = 0; r < (int)in[i].size() - 1; r++) {
			G[inx[i] + r].push_back({inx[i] + r + 1, in[i][r + 1] - in[i][r]});
			G[inx[i] + r + 1].push_back({inx[i] + r, in[i][r + 1] - in[i][r]});
		}
	}
	// for(int i = 0; i < n; i++) {
	// 	cout << "cur: " << i << '\n';
	// 	cout << '[';
	// 	for(int t : in[i]) 
	// 		cout << t << " ";
	// 	cout << ']';
	// 	cout << '\n';
	// }
	for(int i = 0; i < m; i++) {
		vector<int> ver;
		// cout << "seg: " << l[i] << ' ' << r[i] << ' ' << y[i] << '\n';
		for(int st = l[i]; st <= r[i]; st++) {
			if(h[st] >= y[i]) {
				ver.push_back(st);
				// cout << '[' << st << ' ' << find(in[st].begin(), in[st].end(), y[i]) - in[st].begin() << ']' << ' ';
			}
		}
		// cout << '\n';
		for(int z = 0; z < (int)ver.size() - 1; z++) {
			int st = ver[z], next = ver[z + 1];
			int pos1 = find(in[st].begin(), in[st].end(), y[i]) - in[st].begin();
			int pos2 = find(in[next].begin(), in[next].end(), y[i]) - in[next].begin();
			G[inx[st] + pos1].push_back({inx[next] + pos2, x[next] - x[st]});
			G[inx[next] + pos2].push_back({inx[st] + pos1, x[next] - x[st]});
		}
		// cout << '\n';
	}
	int T = inx[n - 1] + (int)in[n - 1].size();

	vector<ll> dist(T, INF);
	dist[inx[g]] = 0;
	set<pair<ll, int>> st;
	for(int i = 0; i < T; i++) {
		st.insert({dist[i], i});
	}
	while(!st.empty()) {
		int s = st.begin()->second;
		st.erase(st.begin());
		for(auto [to, w] : G[s]) {
			if(dist[to] > dist[s] + w) {
				st.erase({dist[to], to});
				dist[to] = dist[s] + w;
				st.insert({dist[to], to});
			}
		}
	}
	int fin = inx[s];
	if(dist[fin] == INF) return -1;
	return dist[fin];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 49624 KB Output is correct
2 Correct 21 ms 49568 KB Output is correct
3 Correct 25 ms 49540 KB Output is correct
4 Correct 21 ms 49620 KB Output is correct
5 Correct 23 ms 49608 KB Output is correct
6 Correct 25 ms 49636 KB Output is correct
7 Correct 25 ms 49644 KB Output is correct
8 Correct 21 ms 49620 KB Output is correct
9 Correct 21 ms 49624 KB Output is correct
10 Correct 22 ms 49736 KB Output is correct
11 Correct 21 ms 49616 KB Output is correct
12 Correct 21 ms 49540 KB Output is correct
13 Correct 21 ms 49576 KB Output is correct
14 Correct 26 ms 49616 KB Output is correct
15 Correct 22 ms 49612 KB Output is correct
16 Correct 29 ms 49740 KB Output is correct
17 Correct 27 ms 49692 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 49580 KB Output is correct
2 Correct 20 ms 49620 KB Output is correct
3 Correct 1124 ms 170916 KB Output is correct
4 Correct 971 ms 184300 KB Output is correct
5 Correct 624 ms 166596 KB Output is correct
6 Correct 1559 ms 153596 KB Output is correct
7 Correct 594 ms 166840 KB Output is correct
8 Correct 1627 ms 203732 KB Output is correct
9 Correct 860 ms 164700 KB Output is correct
10 Correct 1505 ms 233908 KB Output is correct
11 Correct 534 ms 117144 KB Output is correct
12 Correct 362 ms 100864 KB Output is correct
13 Correct 1201 ms 211876 KB Output is correct
14 Execution timed out 4051 ms 75152 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 69972 KB Output is correct
2 Runtime error 449 ms 351948 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 69972 KB Output is correct
2 Runtime error 449 ms 351948 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 49624 KB Output is correct
2 Correct 21 ms 49568 KB Output is correct
3 Correct 25 ms 49540 KB Output is correct
4 Correct 21 ms 49620 KB Output is correct
5 Correct 23 ms 49608 KB Output is correct
6 Correct 25 ms 49636 KB Output is correct
7 Correct 25 ms 49644 KB Output is correct
8 Correct 21 ms 49620 KB Output is correct
9 Correct 21 ms 49624 KB Output is correct
10 Correct 22 ms 49736 KB Output is correct
11 Correct 21 ms 49616 KB Output is correct
12 Correct 21 ms 49540 KB Output is correct
13 Correct 21 ms 49576 KB Output is correct
14 Correct 26 ms 49616 KB Output is correct
15 Correct 22 ms 49612 KB Output is correct
16 Correct 29 ms 49740 KB Output is correct
17 Correct 27 ms 49692 KB Output is correct
18 Correct 21 ms 49580 KB Output is correct
19 Correct 20 ms 49620 KB Output is correct
20 Correct 1124 ms 170916 KB Output is correct
21 Correct 971 ms 184300 KB Output is correct
22 Correct 624 ms 166596 KB Output is correct
23 Correct 1559 ms 153596 KB Output is correct
24 Correct 594 ms 166840 KB Output is correct
25 Correct 1627 ms 203732 KB Output is correct
26 Correct 860 ms 164700 KB Output is correct
27 Correct 1505 ms 233908 KB Output is correct
28 Correct 534 ms 117144 KB Output is correct
29 Correct 362 ms 100864 KB Output is correct
30 Correct 1201 ms 211876 KB Output is correct
31 Execution timed out 4051 ms 75152 KB Time limit exceeded
32 Halted 0 ms 0 KB -