oj.uz

Submission #770336

# Submission time Handle Problem Language Result Execution time Memory
770336 2023-07-01T05:45:46 Z SanguineChameleon Sky Walking (IOI19_walk) C++17
10 / 100
 1520 ms 527720 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 * 2];
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 21 ms 40200 KB Output is correct
2 Correct 19 ms 40184 KB Output is correct
3 Correct 20 ms 40176 KB Output is correct
4 Correct 20 ms 40276 KB Output is correct
5 Correct 21 ms 40336 KB Output is correct
6 Correct 20 ms 40336 KB Output is correct
7 Correct 20 ms 40276 KB Output is correct
8 Correct 20 ms 40352 KB Output is correct
9 Correct 20 ms 40288 KB Output is correct
10 Correct 21 ms 40380 KB Output is correct
11 Correct 18 ms 40312 KB Output is correct
12 Correct 20 ms 40272 KB Output is correct
13 Correct 20 ms 40272 KB Output is correct
14 Correct 20 ms 40244 KB Output is correct
15 Correct 19 ms 40276 KB Output is correct
16 Correct 19 ms 40252 KB Output is correct
17 Correct 21 ms 40404 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 40276 KB Output is correct
2 Correct 19 ms 40148 KB Output is correct
3 Correct 1520 ms 166388 KB Output is correct
4 Incorrect 1312 ms 191652 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 64204 KB Output is correct
2 Runtime error 1392 ms 527720 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 153 ms 64204 KB Output is correct
2 Runtime error 1392 ms 527720 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 21 ms 40200 KB Output is correct
2 Correct 19 ms 40184 KB Output is correct
3 Correct 20 ms 40176 KB Output is correct
4 Correct 20 ms 40276 KB Output is correct
5 Correct 21 ms 40336 KB Output is correct
6 Correct 20 ms 40336 KB Output is correct
7 Correct 20 ms 40276 KB Output is correct
8 Correct 20 ms 40352 KB Output is correct
9 Correct 20 ms 40288 KB Output is correct
10 Correct 21 ms 40380 KB Output is correct
11 Correct 18 ms 40312 KB Output is correct
12 Correct 20 ms 40272 KB Output is correct
13 Correct 20 ms 40272 KB Output is correct
14 Correct 20 ms 40244 KB Output is correct
15 Correct 19 ms 40276 KB Output is correct
16 Correct 19 ms 40252 KB Output is correct
17 Correct 21 ms 40404 KB Output is correct
18 Correct 20 ms 40276 KB Output is correct
19 Correct 19 ms 40148 KB Output is correct
20 Correct 1520 ms 166388 KB Output is correct
21 Incorrect 1312 ms 191652 KB Output isn't correct
22 Halted 0 ms 0 KB -