oj.uz

Submission #770361

# Submission time Handle Problem Language Result Execution time Memory
770361 2023-07-01T06:03:01 Z SanguineChameleon Sky Walking (IOI19_walk) C++17
33 / 100
 1370 ms 146184 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();
	bool sub34 = (_S == 0 && _T == N - 1) || true;
	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 <= N + M; i++) {
		Y[i] = orderY[i].first;
		H[orderY[i].second] = i;
	}
	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> walks;
	for (int i = 1; i <= N; i++) {
		col[i].push_back(0);
		col[i].push_back(H[M + i]);
		for (auto id: qadd[i]) {
			walks.insert(H[id]);
		}
		if (sub34) {
			for (auto id: qadd[i]) {
				col[i].push_back(H[id]);
				row[H[id]].push_back(i);
				auto it = walks.lower_bound(H[id]);
				if (it != walks.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 = walks.lower_bound(H[id]);
				if (it != walks.begin()) {
					it--;
					col[i].push_back(*it);
					row[*it].push_back(i);
				}
			}
		}
		else {
			auto it = walks.upper_bound(H[M + i]);
			while (it != walks.begin()) {
				it--;
				col[i].push_back(*it);
				row[*it].push_back(i);
			}
		}
		for (auto id: qrem[i]) {
			walks.erase(H[id]);
		}
	}
	for (int i = 1; i <= N; i++) {
		sort(col[i].begin(), 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());
		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]);
		}
	}
	int S = get_id(_S + 1, 0);
	int T = get_id(_T + 1, 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 40240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 40276 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 67472 KB Output is correct
2 Correct 849 ms 110828 KB Output is correct
3 Correct 877 ms 116528 KB Output is correct
4 Correct 1135 ms 145560 KB Output is correct
5 Correct 1295 ms 144900 KB Output is correct
6 Correct 1232 ms 142596 KB Output is correct
7 Correct 547 ms 108904 KB Output is correct
8 Correct 505 ms 116680 KB Output is correct
9 Correct 1317 ms 141560 KB Output is correct
10 Correct 638 ms 118676 KB Output is correct
11 Correct 59 ms 54572 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 67472 KB Output is correct
2 Correct 849 ms 110828 KB Output is correct
3 Correct 877 ms 116528 KB Output is correct
4 Correct 1135 ms 145560 KB Output is correct
5 Correct 1295 ms 144900 KB Output is correct
6 Correct 1232 ms 142596 KB Output is correct
7 Correct 547 ms 108904 KB Output is correct
8 Correct 505 ms 116680 KB Output is correct
9 Correct 1317 ms 141560 KB Output is correct
10 Correct 638 ms 118676 KB Output is correct
11 Correct 59 ms 54572 KB Output is correct
12 Correct 892 ms 116528 KB Output is correct
13 Correct 984 ms 144372 KB Output is correct
14 Correct 1308 ms 144868 KB Output is correct
15 Correct 981 ms 135828 KB Output is correct
16 Correct 899 ms 135908 KB Output is correct
17 Correct 1027 ms 146184 KB Output is correct
18 Correct 987 ms 135828 KB Output is correct
19 Correct 893 ms 135988 KB Output is correct
20 Correct 611 ms 108172 KB Output is correct
21 Correct 120 ms 69840 KB Output is correct
22 Correct 706 ms 128972 KB Output is correct
23 Correct 656 ms 127396 KB Output is correct
24 Correct 502 ms 116184 KB Output is correct
25 Correct 555 ms 122912 KB Output is correct
26 Correct 456 ms 110412 KB Output is correct
27 Correct 1370 ms 145444 KB Output is correct
28 Correct 845 ms 143812 KB Output is correct
29 Correct 1289 ms 142600 KB Output is correct
30 Correct 571 ms 109376 KB Output is correct
31 Correct 1178 ms 139428 KB Output is correct
32 Correct 553 ms 112824 KB Output is correct
33 Correct 588 ms 117312 KB Output is correct
34 Correct 724 ms 119692 KB Output is correct
35 Correct 640 ms 120356 KB Output is correct
36 Correct 537 ms 114852 KB Output is correct
37 Correct 463 ms 108236 KB Output is correct
38 Correct 497 ms 115788 KB Output is correct
39 Correct 739 ms 123088 KB Output is correct
40 Correct 520 ms 114184 KB Output is correct
41 Correct 467 ms 111468 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 40240 KB Output isn't correct
2 Halted 0 ms 0 KB -