oj.uz

Submission #770330

# Submission time Handle Problem Language Result Execution time Memory
770330 2023-07-01T05:41:49 Z SanguineChameleon Sky Walking (IOI19_walk) C++17
10 / 100
 2807 ms 767024 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 * 20;
int X[maxN];
int Y[maxN * 2];
int H[maxN * 2];
int L[maxN];
int R[maxN];
pair<int, int> orderY[maxN];
vector<int> qadd[maxN];
vector<int> qrem[maxN];
vector<int> row[maxN];
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]);
		}
		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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 56692 KB Output is correct
2 Correct 25 ms 56692 KB Output is correct
3 Correct 24 ms 56676 KB Output is correct
4 Correct 25 ms 56724 KB Output is correct
5 Correct 25 ms 56820 KB Output is correct
6 Correct 25 ms 56788 KB Output is correct
7 Correct 26 ms 56688 KB Output is correct
8 Correct 26 ms 56780 KB Output is correct
9 Correct 25 ms 56680 KB Output is correct
10 Correct 25 ms 56788 KB Output is correct
11 Correct 28 ms 56708 KB Output is correct
12 Correct 28 ms 56640 KB Output is correct
13 Correct 27 ms 56644 KB Output is correct
14 Correct 25 ms 56660 KB Output is correct
15 Correct 24 ms 56704 KB Output is correct
16 Correct 25 ms 56684 KB Output is correct
17 Correct 25 ms 56788 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 56620 KB Output is correct
2 Correct 25 ms 56660 KB Output is correct
3 Correct 1604 ms 183272 KB Output is correct
4 Incorrect 1345 ms 211436 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 81208 KB Output is correct
2 Runtime error 2807 ms 767024 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 176 ms 81208 KB Output is correct
2 Runtime error 2807 ms 767024 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 25 ms 56692 KB Output is correct
2 Correct 25 ms 56692 KB Output is correct
3 Correct 24 ms 56676 KB Output is correct
4 Correct 25 ms 56724 KB Output is correct
5 Correct 25 ms 56820 KB Output is correct
6 Correct 25 ms 56788 KB Output is correct
7 Correct 26 ms 56688 KB Output is correct
8 Correct 26 ms 56780 KB Output is correct
9 Correct 25 ms 56680 KB Output is correct
10 Correct 25 ms 56788 KB Output is correct
11 Correct 28 ms 56708 KB Output is correct
12 Correct 28 ms 56640 KB Output is correct
13 Correct 27 ms 56644 KB Output is correct
14 Correct 25 ms 56660 KB Output is correct
15 Correct 24 ms 56704 KB Output is correct
16 Correct 25 ms 56684 KB Output is correct
17 Correct 25 ms 56788 KB Output is correct
18 Correct 25 ms 56620 KB Output is correct
19 Correct 25 ms 56660 KB Output is correct
20 Correct 1604 ms 183272 KB Output is correct
21 Incorrect 1345 ms 211436 KB Output isn't correct
22 Halted 0 ms 0 KB -