oj.uz

Submission #770335

# Submission time Handle Problem Language Result Execution time Memory
770335 2023-07-01T05:45:05 Z SanguineChameleon Sky Walking (IOI19_walk) C++17
10 / 100
 1558 ms 525224 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];
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 22 ms 37892 KB Output is correct
2 Correct 24 ms 37916 KB Output is correct
3 Correct 18 ms 37876 KB Output is correct
4 Correct 20 ms 37860 KB Output is correct
5 Correct 20 ms 37920 KB Output is correct
6 Correct 19 ms 38000 KB Output is correct
7 Correct 18 ms 37972 KB Output is correct
8 Correct 18 ms 37984 KB Output is correct
9 Correct 18 ms 37872 KB Output is correct
10 Correct 18 ms 37988 KB Output is correct
11 Correct 23 ms 37928 KB Output is correct
12 Correct 19 ms 37920 KB Output is correct
13 Correct 24 ms 37836 KB Output is correct
14 Correct 18 ms 37844 KB Output is correct
15 Correct 17 ms 37844 KB Output is correct
16 Correct 18 ms 37940 KB Output is correct
17 Correct 18 ms 37972 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 37888 KB Output is correct
2 Correct 18 ms 37868 KB Output is correct
3 Correct 1558 ms 163940 KB Output is correct
4 Incorrect 1344 ms 189380 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 61900 KB Output is correct
2 Runtime error 1291 ms 525224 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 156 ms 61900 KB Output is correct
2 Runtime error 1291 ms 525224 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 22 ms 37892 KB Output is correct
2 Correct 24 ms 37916 KB Output is correct
3 Correct 18 ms 37876 KB Output is correct
4 Correct 20 ms 37860 KB Output is correct
5 Correct 20 ms 37920 KB Output is correct
6 Correct 19 ms 38000 KB Output is correct
7 Correct 18 ms 37972 KB Output is correct
8 Correct 18 ms 37984 KB Output is correct
9 Correct 18 ms 37872 KB Output is correct
10 Correct 18 ms 37988 KB Output is correct
11 Correct 23 ms 37928 KB Output is correct
12 Correct 19 ms 37920 KB Output is correct
13 Correct 24 ms 37836 KB Output is correct
14 Correct 18 ms 37844 KB Output is correct
15 Correct 17 ms 37844 KB Output is correct
16 Correct 18 ms 37940 KB Output is correct
17 Correct 18 ms 37972 KB Output is correct
18 Correct 17 ms 37888 KB Output is correct
19 Correct 18 ms 37868 KB Output is correct
20 Correct 1558 ms 163940 KB Output is correct
21 Incorrect 1344 ms 189380 KB Output isn't correct
22 Halted 0 ms 0 KB -