oj.uz

Submission #826693

# Submission time Handle Problem Language Result Execution time Memory
826693 2023-08-15T20:55:22 Z happypotato Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 56 ms 86724 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});
	dist[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 42 ms 83272 KB Output is correct
2 Correct 48 ms 83296 KB Output is correct
3 Correct 49 ms 83276 KB Output is correct
4 Correct 45 ms 83272 KB Output is correct
5 Correct 45 ms 83268 KB Output is correct
6 Correct 50 ms 83280 KB Output is correct
7 Correct 52 ms 83328 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 83256 KB Output is correct
2 Correct 46 ms 83284 KB Output is correct
3 Correct 47 ms 83340 KB Output is correct
4 Correct 50 ms 83288 KB Output is correct
5 Correct 48 ms 83292 KB Output is correct
6 Correct 45 ms 83348 KB Output is correct
7 Correct 47 ms 83276 KB Output is correct
8 Correct 48 ms 83396 KB Output is correct
9 Correct 47 ms 83504 KB Output is correct
10 Correct 51 ms 83560 KB Output is correct
11 Correct 49 ms 83680 KB Output is correct
12 Correct 52 ms 83656 KB Output is correct
13 Correct 50 ms 83624 KB Output is correct
14 Correct 49 ms 83688 KB Output is correct
15 Correct 52 ms 83668 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 83308 KB Output is correct
2 Correct 47 ms 83316 KB Output is correct
3 Correct 48 ms 83264 KB Output is correct
4 Correct 47 ms 83336 KB Output is correct
5 Correct 50 ms 83344 KB Output is correct
6 Correct 50 ms 83268 KB Output is correct
7 Correct 49 ms 83260 KB Output is correct
8 Correct 49 ms 83400 KB Output is correct
9 Correct 46 ms 83440 KB Output is correct
10 Correct 46 ms 83620 KB Output is correct
11 Correct 51 ms 83628 KB Output is correct
12 Correct 45 ms 83676 KB Output is correct
13 Correct 47 ms 83704 KB Output is correct
14 Correct 48 ms 83736 KB Output is correct
15 Correct 50 ms 83716 KB Output is correct
16 Correct 49 ms 84000 KB Output is correct
17 Incorrect 53 ms 86724 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 83256 KB Output is correct
2 Correct 45 ms 83316 KB Output is correct
3 Correct 48 ms 83336 KB Output is correct
4 Correct 49 ms 83276 KB Output is correct
5 Correct 48 ms 83280 KB Output is correct
6 Correct 48 ms 83336 KB Output is correct
7 Correct 46 ms 83264 KB Output is correct
8 Correct 48 ms 83408 KB Output is correct
9 Correct 47 ms 83404 KB Output is correct
10 Correct 50 ms 83660 KB Output is correct
11 Correct 47 ms 83688 KB Output is correct
12 Correct 52 ms 83648 KB Output is correct
13 Correct 50 ms 83700 KB Output is correct
14 Correct 52 ms 83684 KB Output is correct
15 Correct 46 ms 83628 KB Output is correct
16 Correct 46 ms 84048 KB Output is correct
17 Incorrect 56 ms 86656 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 83308 KB Output is correct
2 Correct 51 ms 83276 KB Output is correct
3 Correct 48 ms 83308 KB Output is correct
4 Correct 43 ms 83268 KB Output is correct
5 Correct 43 ms 83240 KB Output is correct
6 Correct 51 ms 83332 KB Output is correct
7 Correct 53 ms 83276 KB Output is correct
8 Correct 46 ms 83412 KB Output is correct
9 Correct 47 ms 83504 KB Output is correct
10 Correct 53 ms 83752 KB Output is correct
11 Correct 48 ms 83660 KB Output is correct
12 Correct 47 ms 83660 KB Output is correct
13 Correct 47 ms 83788 KB Output is correct
14 Correct 47 ms 83700 KB Output is correct
15 Correct 48 ms 83668 KB Output is correct
16 Correct 48 ms 84104 KB Output is correct
17 Incorrect 53 ms 86656 KB Output isn't correct
18 Halted 0 ms 0 KB -