oj.uz

Submission #770441

# Submission time Handle Problem Language Result Execution time Memory
770441 2023-07-01T08:04:32 Z SanguineChameleon Sky Walking (IOI19_walk) C++17
100 / 100
 2339 ms 195528 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

const long long inf = 1e18L + 20;
const int maxN = 1e5 + 20;
const int max_nodes = maxN * 12;
int X[maxN];
int Y[maxN * 2];
int H[maxN * 2];
int L[maxN];
int R[maxN];
pair<int, int> orderY[maxN * 2];
vector<int> qadd[maxN];
vector<int> qrem[maxN];
vector<int> row[maxN * 2];
vector<int> col[maxN];
long long dist[max_nodes];
vector<pair<int, int>> adj[max_nodes];
map<pair<int, int>, int> points;
int node_cnt;

int get_id(int i, int j) {
	auto it = points.find(make_pair(i, j));
	if (it == points.end()) {
		return points[make_pair(i, j)] = ++node_cnt;
	}
	else {
		return it->second;
	}
}

void add_edge(int i1, int j1, int i2, int j2) {
	int u = get_id(i1, j1);
	int v = get_id(i2, j2);
	int w = abs(X[i1] - X[i2]) + abs(Y[j1] - Y[j2]);
	adj[u].emplace_back(v, w);
	adj[v].emplace_back(u, w);
}

long long min_distance(vector<int> _X, vector<int> _H, vector<int> _L, vector<int> _R, vector<int> _Y, int S, int T) {
	int N = _X.size();
	int M = _L.size();
	for (int i = 1; i <= N; i++) {
		X[i] = _X[i - 1];
	}
	for (int i = 1; i <= M; i++) {
		orderY[i] = make_pair(_Y[i - 1], i);
	}
	for (int i = M + 1; i <= M + N; i++) {
		orderY[i] = make_pair(_H[i - M - 1], i);
	}
	sort(orderY + 1, orderY + N + M + 1);
	for (int i = 1; i <= M; i++) {
		L[i] = _L[i - 1] + 1;
		R[i] = _R[i - 1] + 1;
		qadd[L[i]].push_back(i);
		qrem[R[i]].push_back(i);
	}
	set<int> buildings;
	for (int i = 1; i <= N; i++) {
		buildings.insert(i);
	}
	S++;
	T++;
	for (int i = 1; i <= N + M; i++) {
		Y[i] = orderY[i].first;
		int id = orderY[i].second;
		H[id] = i;
		if (id <= M) {
			if (L[id] < S && S < R[id]) {
				auto it = buildings.lower_bound(S);
				qadd[*it].push_back(id);
				qadd[*prev(it)].push_back(id);
			}
			if (L[id] < T && T < R[id]) {
				auto it = buildings.lower_bound(T);
				qadd[*it].push_back(id);
				qadd[*prev(it)].push_back(id);
			}
		}
		else {
			buildings.erase(id - M);
		}
	}
	set<int> skywalks;
	for (int i = 1; i <= N; i++) {
		col[i].push_back(0);
		col[i].push_back(H[M + i]);
		for (auto id: qadd[i]) {
			skywalks.insert(H[id]);
		}
		for (auto id: qadd[i]) {
			col[i].push_back(H[id]);
			row[H[id]].push_back(i);
			auto it = skywalks.lower_bound(H[id]);
			if (it != skywalks.begin()) {
				it--;
				col[i].push_back(*it);
				row[*it].push_back(i);
			}
		}
		for (auto id: qrem[i]) {
			col[i].push_back(H[id]);
			row[H[id]].push_back(i);
			auto it = skywalks.lower_bound(H[id]);
			if (it != skywalks.begin()) {
				it--;
				col[i].push_back(*it);
				row[*it].push_back(i);
			}
		}
		for (auto id: qrem[i]) {
			skywalks.erase(H[id]);
		}
	}
	for (int i = 1; i <= N; i++) {
		sort(col[i].begin(), col[i].end());
		col[i].erase(unique(col[i].begin(), col[i].end()), col[i].end());
		for (int j = 0; j < (int)col[i].size() - 1; j++) {
			add_edge(i, col[i][j], i, col[i][j + 1]);
		}
	}
	for (int i = 1; i <= M; i++) {
		sort(row[H[i]].begin(), row[H[i]].end());
		row[H[i]].erase(unique(row[H[i]].begin(), row[H[i]].end()), row[H[i]].end());
		for (int j = 0; j < (int)row[H[i]].size() - 1; j++) {
			add_edge(row[H[i]][j], H[i], row[H[i]][j + 1], H[i]);
		}
	}
	S = get_id(S, 0);
	T = get_id(T, 0);
	for (int i = 1; i <= node_cnt; i++) {
		dist[i] = inf;
	}
	dist[S] = 0;
	priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> Q;
	Q.emplace(0, S);
	while (!Q.empty()) {
		int u = Q.top().second;
		if (Q.top().first != dist[u]) {
			Q.pop();
			continue;
		}
		Q.pop();
		for (auto e: adj[u]) {
			int v = e.first;
			int w = e.second;
			if (dist[u] + w < dist[v]) {
				dist[v] = dist[u] + w;
				Q.emplace(dist[v], v);
			}
		}
	}
	if (dist[T] == inf) {
		return -1;
	}
	else {
		return dist[T];
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 40276 KB Output is correct
2 Correct 19 ms 40268 KB Output is correct
3 Correct 18 ms 40276 KB Output is correct
4 Correct 19 ms 40280 KB Output is correct
5 Correct 19 ms 40316 KB Output is correct
6 Correct 19 ms 40192 KB Output is correct
7 Correct 19 ms 40248 KB Output is correct
8 Correct 21 ms 40224 KB Output is correct
9 Correct 19 ms 40320 KB Output is correct
10 Correct 19 ms 40276 KB Output is correct
11 Correct 21 ms 40244 KB Output is correct
12 Correct 19 ms 40272 KB Output is correct
13 Correct 19 ms 40188 KB Output is correct
14 Correct 20 ms 40284 KB Output is correct
15 Correct 18 ms 40224 KB Output is correct
16 Correct 19 ms 40216 KB Output is correct
17 Correct 19 ms 40284 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 40276 KB Output is correct
2 Correct 19 ms 40260 KB Output is correct
3 Correct 725 ms 106280 KB Output is correct
4 Correct 776 ms 135880 KB Output is correct
5 Correct 553 ms 118076 KB Output is correct
6 Correct 574 ms 116612 KB Output is correct
7 Correct 576 ms 118252 KB Output is correct
8 Correct 728 ms 108752 KB Output is correct
9 Correct 699 ms 125576 KB Output is correct
10 Correct 863 ms 135216 KB Output is correct
11 Correct 616 ms 107204 KB Output is correct
12 Correct 515 ms 116572 KB Output is correct
13 Correct 893 ms 140008 KB Output is correct
14 Correct 526 ms 115696 KB Output is correct
15 Correct 548 ms 115928 KB Output is correct
16 Correct 495 ms 113668 KB Output is correct
17 Correct 515 ms 111320 KB Output is correct
18 Correct 595 ms 111804 KB Output is correct
19 Correct 33 ms 43860 KB Output is correct
20 Correct 198 ms 76868 KB Output is correct
21 Correct 456 ms 106612 KB Output is correct
22 Correct 479 ms 115688 KB Output is correct
23 Correct 694 ms 122944 KB Output is correct
24 Correct 537 ms 113804 KB Output is correct
25 Correct 473 ms 111184 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 64356 KB Output is correct
2 Correct 845 ms 110260 KB Output is correct
3 Correct 888 ms 114380 KB Output is correct
4 Correct 1147 ms 141556 KB Output is correct
5 Correct 1207 ms 140908 KB Output is correct
6 Correct 1161 ms 138700 KB Output is correct
7 Correct 574 ms 105932 KB Output is correct
8 Correct 488 ms 112756 KB Output is correct
9 Correct 1133 ms 137632 KB Output is correct
10 Correct 559 ms 111072 KB Output is correct
11 Correct 65 ms 53928 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 64356 KB Output is correct
2 Correct 845 ms 110260 KB Output is correct
3 Correct 888 ms 114380 KB Output is correct
4 Correct 1147 ms 141556 KB Output is correct
5 Correct 1207 ms 140908 KB Output is correct
6 Correct 1161 ms 138700 KB Output is correct
7 Correct 574 ms 105932 KB Output is correct
8 Correct 488 ms 112756 KB Output is correct
9 Correct 1133 ms 137632 KB Output is correct
10 Correct 559 ms 111072 KB Output is correct
11 Correct 65 ms 53928 KB Output is correct
12 Correct 890 ms 114504 KB Output is correct
13 Correct 997 ms 140544 KB Output is correct
14 Correct 1179 ms 141188 KB Output is correct
15 Correct 862 ms 132000 KB Output is correct
16 Correct 863 ms 132132 KB Output is correct
17 Correct 1044 ms 142024 KB Output is correct
18 Correct 857 ms 132056 KB Output is correct
19 Correct 912 ms 132056 KB Output is correct
20 Correct 678 ms 105196 KB Output is correct
21 Correct 147 ms 68024 KB Output is correct
22 Correct 711 ms 125336 KB Output is correct
23 Correct 645 ms 123876 KB Output is correct
24 Correct 514 ms 112756 KB Output is correct
25 Correct 619 ms 119576 KB Output is correct
26 Correct 466 ms 106792 KB Output is correct
27 Correct 1292 ms 141500 KB Output is correct
28 Correct 919 ms 139912 KB Output is correct
29 Correct 1151 ms 138764 KB Output is correct
30 Correct 577 ms 106448 KB Output is correct
31 Correct 1157 ms 135512 KB Output is correct
32 Correct 508 ms 107592 KB Output is correct
33 Correct 521 ms 111804 KB Output is correct
34 Correct 613 ms 115304 KB Output is correct
35 Correct 660 ms 117304 KB Output is correct
36 Correct 523 ms 112040 KB Output is correct
37 Correct 421 ms 104012 KB Output is correct
38 Correct 476 ms 112724 KB Output is correct
39 Correct 677 ms 120132 KB Output is correct
40 Correct 526 ms 110856 KB Output is correct
41 Correct 461 ms 108632 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 40276 KB Output is correct
2 Correct 19 ms 40268 KB Output is correct
3 Correct 18 ms 40276 KB Output is correct
4 Correct 19 ms 40280 KB Output is correct
5 Correct 19 ms 40316 KB Output is correct
6 Correct 19 ms 40192 KB Output is correct
7 Correct 19 ms 40248 KB Output is correct
8 Correct 21 ms 40224 KB Output is correct
9 Correct 19 ms 40320 KB Output is correct
10 Correct 19 ms 40276 KB Output is correct
11 Correct 21 ms 40244 KB Output is correct
12 Correct 19 ms 40272 KB Output is correct
13 Correct 19 ms 40188 KB Output is correct
14 Correct 20 ms 40284 KB Output is correct
15 Correct 18 ms 40224 KB Output is correct
16 Correct 19 ms 40216 KB Output is correct
17 Correct 19 ms 40284 KB Output is correct
18 Correct 19 ms 40276 KB Output is correct
19 Correct 19 ms 40260 KB Output is correct
20 Correct 725 ms 106280 KB Output is correct
21 Correct 776 ms 135880 KB Output is correct
22 Correct 553 ms 118076 KB Output is correct
23 Correct 574 ms 116612 KB Output is correct
24 Correct 576 ms 118252 KB Output is correct
25 Correct 728 ms 108752 KB Output is correct
26 Correct 699 ms 125576 KB Output is correct
27 Correct 863 ms 135216 KB Output is correct
28 Correct 616 ms 107204 KB Output is correct
29 Correct 515 ms 116572 KB Output is correct
30 Correct 893 ms 140008 KB Output is correct
31 Correct 526 ms 115696 KB Output is correct
32 Correct 548 ms 115928 KB Output is correct
33 Correct 495 ms 113668 KB Output is correct
34 Correct 515 ms 111320 KB Output is correct
35 Correct 595 ms 111804 KB Output is correct
36 Correct 33 ms 43860 KB Output is correct
37 Correct 198 ms 76868 KB Output is correct
38 Correct 456 ms 106612 KB Output is correct
39 Correct 479 ms 115688 KB Output is correct
40 Correct 694 ms 122944 KB Output is correct
41 Correct 537 ms 113804 KB Output is correct
42 Correct 473 ms 111184 KB Output is correct
43 Correct 190 ms 64356 KB Output is correct
44 Correct 845 ms 110260 KB Output is correct
45 Correct 888 ms 114380 KB Output is correct
46 Correct 1147 ms 141556 KB Output is correct
47 Correct 1207 ms 140908 KB Output is correct
48 Correct 1161 ms 138700 KB Output is correct
49 Correct 574 ms 105932 KB Output is correct
50 Correct 488 ms 112756 KB Output is correct
51 Correct 1133 ms 137632 KB Output is correct
52 Correct 559 ms 111072 KB Output is correct
53 Correct 65 ms 53928 KB Output is correct
54 Correct 890 ms 114504 KB Output is correct
55 Correct 997 ms 140544 KB Output is correct
56 Correct 1179 ms 141188 KB Output is correct
57 Correct 862 ms 132000 KB Output is correct
58 Correct 863 ms 132132 KB Output is correct
59 Correct 1044 ms 142024 KB Output is correct
60 Correct 857 ms 132056 KB Output is correct
61 Correct 912 ms 132056 KB Output is correct
62 Correct 678 ms 105196 KB Output is correct
63 Correct 147 ms 68024 KB Output is correct
64 Correct 711 ms 125336 KB Output is correct
65 Correct 645 ms 123876 KB Output is correct
66 Correct 514 ms 112756 KB Output is correct
67 Correct 619 ms 119576 KB Output is correct
68 Correct 466 ms 106792 KB Output is correct
69 Correct 1292 ms 141500 KB Output is correct
70 Correct 919 ms 139912 KB Output is correct
71 Correct 1151 ms 138764 KB Output is correct
72 Correct 577 ms 106448 KB Output is correct
73 Correct 1157 ms 135512 KB Output is correct
74 Correct 508 ms 107592 KB Output is correct
75 Correct 521 ms 111804 KB Output is correct
76 Correct 613 ms 115304 KB Output is correct
77 Correct 660 ms 117304 KB Output is correct
78 Correct 523 ms 112040 KB Output is correct
79 Correct 421 ms 104012 KB Output is correct
80 Correct 476 ms 112724 KB Output is correct
81 Correct 677 ms 120132 KB Output is correct
82 Correct 526 ms 110856 KB Output is correct
83 Correct 461 ms 108632 KB Output is correct
84 Correct 139 ms 60508 KB Output is correct
85 Correct 1006 ms 120184 KB Output is correct
86 Correct 1782 ms 170860 KB Output is correct
87 Correct 181 ms 75704 KB Output is correct
88 Correct 220 ms 75772 KB Output is correct
89 Correct 180 ms 75728 KB Output is correct
90 Correct 58 ms 48652 KB Output is correct
91 Correct 21 ms 40632 KB Output is correct
92 Correct 48 ms 45860 KB Output is correct
93 Correct 477 ms 96892 KB Output is correct
94 Correct 157 ms 70604 KB Output is correct
95 Correct 774 ms 132168 KB Output is correct
96 Correct 672 ms 128128 KB Output is correct
97 Correct 534 ms 118340 KB Output is correct
98 Correct 611 ms 122904 KB Output is correct
99 Correct 2339 ms 195528 KB Output is correct
100 Correct 1131 ms 145996 KB Output is correct
101 Correct 1644 ms 163448 KB Output is correct
102 Correct 577 ms 109648 KB Output is correct
103 Correct 512 ms 110484 KB Output is correct
104 Correct 562 ms 114860 KB Output is correct
105 Correct 619 ms 118276 KB Output is correct
106 Correct 563 ms 115064 KB Output is correct
107 Correct 596 ms 119272 KB Output is correct
108 Correct 68 ms 48980 KB Output is correct
109 Correct 912 ms 129400 KB Output is correct
110 Correct 968 ms 143332 KB Output is correct
111 Correct 945 ms 143208 KB Output is correct
112 Correct 661 ms 119024 KB Output is correct
113 Correct 555 ms 116756 KB Output is correct