oj.uz

답안 #770328

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
770328 2023-07-01T05:40:06 Z SanguineChameleon Sky Walking (IOI19_walk) C++17
10 / 100
 167 ms 77952 KB 
#include "walk.h"
#include <bits/stdc++.h>
using namespace std;

const long long inf = 1e18L + 20;
const int maxN = 1e5 + 20;
long long dist[maxN * 12];
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];
vector<pair<int, int>> adj[maxN];
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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 12052 KB Output is correct
4 Correct 6 ms 12052 KB Output is correct
5 Correct 7 ms 12180 KB Output is correct
6 Correct 6 ms 12116 KB Output is correct
7 Correct 7 ms 12180 KB Output is correct
8 Correct 7 ms 12052 KB Output is correct
9 Correct 6 ms 12084 KB Output is correct
10 Correct 7 ms 12128 KB Output is correct
11 Correct 6 ms 12096 KB Output is correct
12 Correct 6 ms 12116 KB Output is correct
13 Correct 6 ms 12052 KB Output is correct
14 Correct 8 ms 12052 KB Output is correct
15 Correct 6 ms 12072 KB Output is correct
16 Correct 7 ms 12052 KB Output is correct
17 Correct 8 ms 12180 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12056 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Runtime error 167 ms 77952 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 115 ms 64184 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 115 ms 64184 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 12052 KB Output is correct
4 Correct 6 ms 12052 KB Output is correct
5 Correct 7 ms 12180 KB Output is correct
6 Correct 6 ms 12116 KB Output is correct
7 Correct 7 ms 12180 KB Output is correct
8 Correct 7 ms 12052 KB Output is correct
9 Correct 6 ms 12084 KB Output is correct
10 Correct 7 ms 12128 KB Output is correct
11 Correct 6 ms 12096 KB Output is correct
12 Correct 6 ms 12116 KB Output is correct
13 Correct 6 ms 12052 KB Output is correct
14 Correct 8 ms 12052 KB Output is correct
15 Correct 6 ms 12072 KB Output is correct
16 Correct 7 ms 12052 KB Output is correct
17 Correct 8 ms 12180 KB Output is correct
18 Correct 6 ms 12056 KB Output is correct
19 Correct 7 ms 11988 KB Output is correct
20 Runtime error 167 ms 77952 KB Execution killed with signal 6
21 Halted 0 ms 0 KB -