oj.uz

Submission #585342

# Submission time Handle Problem Language Result Execution time Memory
585342 2022-06-28T17:23:50 Z GusterGoose27 Jakarta Skyscrapers (APIO15_skyscraper) C++11
0 / 100
 2 ms 2516 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 3e4;
const int inf = 1e9;
vector<pii> edges[MAXN];
set<int> at[MAXN];
int n, m;
int dist[MAXN];

void dijkstra() {
	fill(dist, dist+n, inf);
	dist[0] = 0;
	priority_queue<pii> pq;
	pq.push(pii(0, 0));
	while (!pq.empty()) {
		pii p = pq.top();
		pq.pop();
		int cur = p.second;
		if (dist[cur] > p.first) continue;
		for (pii e: edges[cur]) {
			if (dist[cur]+e.second < dist[e.first]) {
				dist[e.first] = dist[cur]+e.second;
				pq.push(pii(dist[e.first], e.first));
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y; cin >> x >> y;
		at[x].insert(y);
	}
	for (int i = n-1; i >= 0; i--) {
		for (int p: at[i]) {
			for (int j = i+p; j < n; j += p) {
				edges[i].push_back(pii(j, (j-i)/p));
				if (at[j].find(p) != at[j].end()) break;
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int p: at[i]) {
			for (int j = i-p; j >= 0; j -= p) {
				edges[i].push_back(pii(j, (i-j)/p));
				if (at[j].find(p) != at[j].end()) break;
			}
		}
	}
	dijkstra();
	cout << ((dist[1] == inf) ? (-1) : dist[1]) << "\n";
	return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 14.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 43.0

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