oj.uz

답안 #350595

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
350595 2021-01-19T06:55:04 Z Fischer Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
 2 ms 2176 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e4 + 10;
priority_queue<int> pos[maxn];
vector<pair<int, int>> g[maxn];
int d[maxn];

int dijkstra(int src, int snk) {
	memset(d, 1, sizeof d);
	d[src] = 0;
	using pii = pair<int, int>;
	priority_queue<pii, vector<pii>, greater<pii>> Q;
	Q.push({0, src});
	while (!Q.empty()) {
		auto q = Q.top(); Q.pop();
		if (q.second == snk) return q.first;
		if (q.first != d[q.second]) continue;
		for (auto e : g[q.second]) {
			int temp = q.first + e.second;
			if (temp < d[e.first]) {
				d[e.first] = temp;
				Q.push({temp, e.first});
			}
		}
	}
	return -1;
}

int main() {
	int n, m;
	cin >> n >> m;
	vector<pair<int, int>> a;
	priority_queue<pair<int, int>> t;
	for (int i = 0; i < m; ++i) {
		int b, p;
		cin >> b >> p;
		t.push({p, b});
		pos[b].push(p);
	}
	auto same = [](int b, int p) {
		return !pos[b].empty() && pos[b].top() == p;	
	};
	while (!t.empty()) {
		auto q = t.top(); t.pop();
		pos[q.second].pop();
		if (same(q.second, q.first)) continue;
		for (int i = 1; ; ++i) {
			int temp = q.second + i * q.first;
			if (temp >= n) break;
			g[q.second].emplace_back(temp, i);
			if (same(temp, q.first)) break;
		}
		for (int i = 1; ; ++i) {
			int temp = q.second - i * q.first;
			if (temp < 0) break;
			g[q.second].emplace_back(temp, i);
			if (same(temp, q.first)) break;
		}
	}
	cout << dijkstra(0, 1) << endl;
	return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2028 KB Output is correct
2 Incorrect 2 ms 2028 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2028 KB Output is correct
2 Incorrect 2 ms 2028 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2028 KB Output is correct
2 Incorrect 2 ms 2028 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2028 KB Output is correct
2 Incorrect 2 ms 2028 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2028 KB Output is correct
2 Incorrect 2 ms 2176 KB Output isn't correct
3 Halted 0 ms 0 KB -