oj.uz

답안 #341818

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
341818 2020-12-31T06:18:08 Z egod1537 Jakarta Skyscrapers (APIO15_skyscraper) C++14
10 / 100
 8 ms 4972 KB 
#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

const int INF = 0x3f3f3f3f;

typedef pair<int, int> pi;
#define to first
#define cost second
#define pos first
#define range second

struct Q {
	int pos, cost;
};
bool operator<(const Q& a, const Q& b) {
	return a.cost > b.cost;
}

vector<pi> V[30001];
unordered_map<int, bool> vit[30001], con[30001];
int dst[30001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	memset(dst, INF, sizeof(dst));

	int n, m; cin >> n >> m;
	vector<pi> doge(m);
	vector<int> posdoge(n + 1, -1);

	int s = 0, e = 0;
	for (int i = 0; i < m; i++) {
		cin >> doge[i].pos >> doge[i].range;
		if (i == 0) s = doge[i].pos;
		if (i == 1) e = doge[i].pos;
		vit[doge[i].pos][doge[i].pos] = true;
	}
	sort(doge.begin(), doge.end(), [](pi& a, pi& b) -> bool {
		if (a.range != b.range) return a.range > b.range;
		return a.pos < b.pos;
		});

	for (int i = 0; i < m; i++) {
		pi& now = doge[i];
		unordered_map<int, bool>& ncon = con[now.pos];
		vector<pi>& nV = V[now.pos];

		for (int j = now.pos + now.range; j < n; j += now.range) {
			if (vit[j].size() == 0 || ncon[j]) continue;
			int dst = j - now.pos;

			nV.push_back({ j, dst / now.range });
			ncon[j] = true;
			if (vit[j][now.range]) break;
		}
		for (int j = now.pos - now.range; j >= 0; j -= now.range) {
			if (vit[j].size() == 0 || ncon[j]) continue;
			int dst = now.pos - j;

			nV.push_back({ j, dst / now.range });
			ncon[j] = true;
			if (vit[j][now.range]) break;
		}
	}

	priority_queue<Q> pq;
	pq.push({ s, 0 });
	while (!pq.empty()) {
		Q top = pq.top(); pq.pop();

		if (top.pos == e) {
			cout << top.cost;
			return 0;
		}

		for (pi w : V[top.pos]) {
			if (dst[w.to] > top.cost + w.cost) {
				dst[w.to] = top.cost + w.cost;
				pq.push({ w.to, dst[w.to] });
			}
		}
	}

	cout << -1;

	return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4460 KB Output is correct
2 Correct 3 ms 4472 KB Output is correct
3 Correct 3 ms 4460 KB Output is correct
4 Correct 3 ms 4460 KB Output is correct
5 Correct 4 ms 4464 KB Output is correct
6 Correct 3 ms 4460 KB Output is correct
7 Correct 3 ms 4460 KB Output is correct

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4460 KB Output is correct
2 Correct 3 ms 4460 KB Output is correct
3 Correct 3 ms 4460 KB Output is correct
4 Correct 3 ms 4460 KB Output is correct
5 Correct 3 ms 4460 KB Output is correct
6 Correct 3 ms 4460 KB Output is correct
7 Correct 3 ms 4460 KB Output is correct
8 Correct 3 ms 4460 KB Output is correct
9 Correct 3 ms 4460 KB Output is correct
10 Correct 4 ms 4608 KB Output is correct
11 Correct 5 ms 4844 KB Output is correct
12 Correct 4 ms 4460 KB Output is correct
13 Correct 7 ms 4972 KB Output is correct
14 Incorrect 4 ms 4588 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4460 KB Output is correct
2 Correct 3 ms 4460 KB Output is correct
3 Correct 3 ms 4460 KB Output is correct
4 Correct 3 ms 4460 KB Output is correct
5 Correct 4 ms 4460 KB Output is correct
6 Correct 4 ms 4460 KB Output is correct
7 Correct 4 ms 4460 KB Output is correct
8 Correct 3 ms 4460 KB Output is correct
9 Correct 4 ms 4460 KB Output is correct
10 Correct 4 ms 4588 KB Output is correct
11 Correct 5 ms 4844 KB Output is correct
12 Correct 4 ms 4460 KB Output is correct
13 Correct 7 ms 4972 KB Output is correct
14 Incorrect 4 ms 4588 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4460 KB Output is correct
2 Correct 4 ms 4460 KB Output is correct
3 Correct 3 ms 4460 KB Output is correct
4 Correct 3 ms 4460 KB Output is correct
5 Correct 4 ms 4460 KB Output is correct
6 Correct 3 ms 4460 KB Output is correct
7 Correct 3 ms 4460 KB Output is correct
8 Correct 3 ms 4460 KB Output is correct
9 Correct 3 ms 4460 KB Output is correct
10 Correct 4 ms 4588 KB Output is correct
11 Correct 5 ms 4844 KB Output is correct
12 Correct 4 ms 4460 KB Output is correct
13 Correct 7 ms 4972 KB Output is correct
14 Incorrect 4 ms 4588 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4460 KB Output is correct
2 Correct 3 ms 4460 KB Output is correct
3 Correct 3 ms 4460 KB Output is correct
4 Correct 4 ms 4460 KB Output is correct
5 Correct 3 ms 4460 KB Output is correct
6 Correct 3 ms 4460 KB Output is correct
7 Correct 4 ms 4460 KB Output is correct
8 Correct 3 ms 4460 KB Output is correct
9 Correct 3 ms 4460 KB Output is correct
10 Correct 4 ms 4588 KB Output is correct
11 Correct 5 ms 4844 KB Output is correct
12 Correct 4 ms 4460 KB Output is correct
13 Correct 8 ms 4972 KB Output is correct
14 Incorrect 4 ms 4588 KB Output isn't correct
15 Halted 0 ms 0 KB -