oj.uz

Submission #350631

# Submission time Handle Problem Language Result Execution time Memory
350631 2021-01-19T07:07:31 Z Fischer Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
 3 ms 2668 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e4 + 10;
set<int> pos[maxn];
vector<pair<int, int>> g[maxn];
using ll = long long;
ll d[maxn];

ll dijkstra(int src, int snk) {
	memset(d, 1, sizeof d);
	d[src] = 0;
	using pii = pair<ll, 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]) {
			ll 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;
	set<pair<int, int>> t;
	for (int i = 0; i < m; ++i) {
		int b, p;
		cin >> b >> p;
		t.insert({p, b});
		pos[b].insert(p);
	}
	auto same = [](int b, int p) {
		return !pos[b].empty() && pos[b].count(p);	
	};
	for (auto q : t) {
		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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Incorrect 2 ms 2668 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Incorrect 3 ms 2668 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2668 KB Output is correct
2 Incorrect 2 ms 2668 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Incorrect 2 ms 2668 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Incorrect 2 ms 2668 KB Output isn't correct
3 Halted 0 ms 0 KB -