oj.uz

Submission #770429

# Submission time Handle Problem Language Result Execution time Memory
770429 2023-07-01T07:56:01 Z SanguineChameleon Sky Walking (IOI19_walk) C++17
33 / 100
 1262 ms 146004 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 <= 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]);
		}
		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);
			}
		}
		for (auto id: qrem[i]) {
			walks.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]);
		}
	}
	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 20 ms 40148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 40268 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 164 ms 64328 KB Output is correct
2 Correct 851 ms 110248 KB Output is correct
3 Correct 837 ms 114508 KB Output is correct
4 Correct 1088 ms 141512 KB Output is correct
5 Correct 1250 ms 144836 KB Output is correct
6 Correct 1131 ms 142652 KB Output is correct
7 Correct 575 ms 108848 KB Output is correct
8 Correct 462 ms 116660 KB Output is correct
9 Correct 1049 ms 141560 KB Output is correct
10 Correct 544 ms 114020 KB Output is correct
11 Correct 57 ms 54476 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 64328 KB Output is correct
2 Correct 851 ms 110248 KB Output is correct
3 Correct 837 ms 114508 KB Output is correct
4 Correct 1088 ms 141512 KB Output is correct
5 Correct 1250 ms 144836 KB Output is correct
6 Correct 1131 ms 142652 KB Output is correct
7 Correct 575 ms 108848 KB Output is correct
8 Correct 462 ms 116660 KB Output is correct
9 Correct 1049 ms 141560 KB Output is correct
10 Correct 544 ms 114020 KB Output is correct
11 Correct 57 ms 54476 KB Output is correct
12 Correct 836 ms 116460 KB Output is correct
13 Correct 996 ms 144452 KB Output is correct
14 Correct 1151 ms 144784 KB Output is correct
15 Correct 911 ms 135744 KB Output is correct
16 Correct 852 ms 136020 KB Output is correct
17 Correct 969 ms 146004 KB Output is correct
18 Correct 880 ms 135776 KB Output is correct
19 Correct 860 ms 136008 KB Output is correct
20 Correct 588 ms 108072 KB Output is correct
21 Correct 117 ms 69816 KB Output is correct
22 Correct 727 ms 128948 KB Output is correct
23 Correct 644 ms 127428 KB Output is correct
24 Correct 485 ms 116404 KB Output is correct
25 Correct 602 ms 123016 KB Output is correct
26 Correct 452 ms 110460 KB Output is correct
27 Correct 1262 ms 145404 KB Output is correct
28 Correct 853 ms 143772 KB Output is correct
29 Correct 1100 ms 142536 KB Output is correct
30 Correct 564 ms 109296 KB Output is correct
31 Correct 1081 ms 139816 KB Output is correct
32 Correct 475 ms 110388 KB Output is correct
33 Correct 505 ms 114868 KB Output is correct
34 Correct 585 ms 118212 KB Output is correct
35 Correct 635 ms 120400 KB Output is correct
36 Correct 507 ms 114800 KB Output is correct
37 Correct 426 ms 106700 KB Output is correct
38 Correct 471 ms 115784 KB Output is correct
39 Correct 658 ms 122888 KB Output is correct
40 Correct 503 ms 113868 KB Output is correct
41 Correct 469 ms 111120 KB Output is correct

Subtask #5
0 / 43.0

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