oj.uz

Submission #826692

# Submission time Handle Problem Language Result Execution time Memory
826692 2023-08-15T20:54:53 Z happypotato Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 55 ms 86728 KB 
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
const int MAX = 1e9;
const int mxN = 3e4;
const int SQRT = 100;
pii doge[mxN];
vector<pii> adj[mxN * (SQRT + 1)];
int dist[mxN * (SQRT + 1)];
void AddEdge(int u, int v, bool w) {
	adj[u].pb({v, w});
}
int n;
void init() {
	for (int i = 0; i < mxN * (SQRT + 1); i++) {
		adj[i].clear();
		dist[i] = MAX;
	}
	// dummy nodes for P_i < SQRT
	for (int diff = 1; diff <= SQRT; diff++) {
		for (int i = 0; i < n; i++) {
			AddEdge(diff * mxN + i, i, 0);
		}
		for (int i = diff; i < n; i++) {
			int u = diff * mxN + (i - diff);
			int v = diff * mxN + i;
			AddEdge(u, v, 1);
			AddEdge(v, u, 1);
		}
	}
}
void solve() {
	int m;
	cin >> n >> m;
	init();
	for (int i = 0; i < m; i++) {
		cin >> doge[i].ff >> doge[i].ss;
		if (doge[i].ss <= SQRT) {
			// connect to dummy nodes
			AddEdge(doge[i].ff, doge[i].ss * mxN + doge[i].ff, 0);
		} else {
			// connect actual edges
			int cur;
			cur = doge[i].ff;
			while (cur + doge[i].ss < n) {
				AddEdge(cur, cur + doge[i].ss, 1);
				cur += doge[i].ss;
			}
			cur = doge[i].ff;
			while (cur - doge[i].ss >= 0) {
				AddEdge(cur, cur - doge[i].ss, 1);
				cur -= doge[i].ss;
			}
		}
	}
	// 0-1 BFS
	deque<pii> dq;
	dq.push_back({doge[0].ff, 0});
	while (!dq.empty()) {
		pii cur = dq.front();
		dq.pop_front();
		for (pii &v : adj[cur.ff]) {
			if (cur.ss + v.ss >= dist[v.ff]) continue;
			dist[v.ff] = cur.ss + v.ss;
			if (!v.ss) dq.push_front({v.ff, dist[v.ff]});
			else dq.push_back({v.ff, dist[v.ff]});
		}
	}
	int ans = dist[doge[1].ff];
	cout << (ans >= MAX ? -1 : ans) << endl;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 83280 KB Output is correct
2 Correct 45 ms 83324 KB Output is correct
3 Correct 45 ms 83312 KB Output is correct
4 Correct 47 ms 83320 KB Output is correct
5 Correct 47 ms 83312 KB Output is correct
6 Correct 46 ms 83340 KB Output is correct
7 Correct 45 ms 83312 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 83272 KB Output is correct
2 Correct 45 ms 83284 KB Output is correct
3 Correct 46 ms 83328 KB Output is correct
4 Correct 47 ms 83276 KB Output is correct
5 Correct 47 ms 83260 KB Output is correct
6 Correct 48 ms 83300 KB Output is correct
7 Correct 47 ms 83320 KB Output is correct
8 Correct 47 ms 83364 KB Output is correct
9 Correct 46 ms 83472 KB Output is correct
10 Correct 47 ms 83660 KB Output is correct
11 Correct 48 ms 83624 KB Output is correct
12 Correct 48 ms 83640 KB Output is correct
13 Correct 47 ms 83624 KB Output is correct
14 Correct 49 ms 83740 KB Output is correct
15 Correct 48 ms 83704 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 83340 KB Output is correct
2 Correct 46 ms 83256 KB Output is correct
3 Correct 45 ms 83272 KB Output is correct
4 Correct 46 ms 83328 KB Output is correct
5 Correct 46 ms 83264 KB Output is correct
6 Correct 46 ms 83268 KB Output is correct
7 Correct 48 ms 83276 KB Output is correct
8 Correct 46 ms 83424 KB Output is correct
9 Correct 50 ms 83480 KB Output is correct
10 Correct 48 ms 83664 KB Output is correct
11 Correct 48 ms 83668 KB Output is correct
12 Correct 48 ms 83668 KB Output is correct
13 Correct 47 ms 83692 KB Output is correct
14 Correct 47 ms 83684 KB Output is correct
15 Correct 48 ms 83664 KB Output is correct
16 Correct 48 ms 84004 KB Output is correct
17 Incorrect 53 ms 86716 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 83340 KB Output is correct
2 Correct 49 ms 83304 KB Output is correct
3 Correct 47 ms 83324 KB Output is correct
4 Correct 46 ms 83260 KB Output is correct
5 Correct 47 ms 83276 KB Output is correct
6 Correct 47 ms 83296 KB Output is correct
7 Correct 54 ms 83272 KB Output is correct
8 Correct 49 ms 83392 KB Output is correct
9 Correct 50 ms 83452 KB Output is correct
10 Correct 47 ms 83604 KB Output is correct
11 Correct 50 ms 83780 KB Output is correct
12 Correct 48 ms 83660 KB Output is correct
13 Correct 48 ms 83676 KB Output is correct
14 Correct 48 ms 83612 KB Output is correct
15 Correct 48 ms 83744 KB Output is correct
16 Correct 51 ms 84028 KB Output is correct
17 Incorrect 54 ms 86628 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 83244 KB Output is correct
2 Correct 50 ms 83220 KB Output is correct
3 Correct 46 ms 83264 KB Output is correct
4 Correct 46 ms 83292 KB Output is correct
5 Correct 55 ms 83236 KB Output is correct
6 Correct 47 ms 83344 KB Output is correct
7 Correct 47 ms 83276 KB Output is correct
8 Correct 46 ms 83428 KB Output is correct
9 Correct 47 ms 83404 KB Output is correct
10 Correct 48 ms 83660 KB Output is correct
11 Correct 53 ms 83752 KB Output is correct
12 Correct 48 ms 83700 KB Output is correct
13 Correct 48 ms 83676 KB Output is correct
14 Correct 46 ms 83716 KB Output is correct
15 Correct 48 ms 83664 KB Output is correct
16 Correct 49 ms 84016 KB Output is correct
17 Incorrect 54 ms 86728 KB Output isn't correct
18 Halted 0 ms 0 KB -