oj.uz

Submission #826691

# Submission time Handle Problem Language Result Execution time Memory
826691 2023-08-15T20:53:58 Z happypotato Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 64 ms 86716 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 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] = 1e9;
	}
	// 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 >= 1e9 ? -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 83284 KB Output is correct
2 Correct 45 ms 83308 KB Output is correct
3 Correct 44 ms 83232 KB Output is correct
4 Correct 44 ms 83336 KB Output is correct
5 Correct 44 ms 83312 KB Output is correct
6 Correct 45 ms 83276 KB Output is correct
7 Correct 45 ms 83324 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 83220 KB Output is correct
2 Correct 45 ms 83240 KB Output is correct
3 Correct 45 ms 83328 KB Output is correct
4 Correct 46 ms 83260 KB Output is correct
5 Correct 46 ms 83344 KB Output is correct
6 Correct 50 ms 83240 KB Output is correct
7 Correct 50 ms 83304 KB Output is correct
8 Correct 47 ms 83380 KB Output is correct
9 Correct 46 ms 83520 KB Output is correct
10 Correct 47 ms 83688 KB Output is correct
11 Correct 48 ms 83700 KB Output is correct
12 Correct 48 ms 83644 KB Output is correct
13 Correct 46 ms 83728 KB Output is correct
14 Correct 47 ms 83660 KB Output is correct
15 Correct 50 ms 83636 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 83252 KB Output is correct
2 Correct 48 ms 83292 KB Output is correct
3 Correct 45 ms 83276 KB Output is correct
4 Correct 45 ms 83272 KB Output is correct
5 Correct 46 ms 83240 KB Output is correct
6 Correct 47 ms 83236 KB Output is correct
7 Correct 46 ms 83288 KB Output is correct
8 Correct 46 ms 83360 KB Output is correct
9 Correct 46 ms 83508 KB Output is correct
10 Correct 48 ms 83656 KB Output is correct
11 Correct 46 ms 83708 KB Output is correct
12 Correct 47 ms 83660 KB Output is correct
13 Correct 47 ms 83720 KB Output is correct
14 Correct 49 ms 83632 KB Output is correct
15 Correct 47 ms 83732 KB Output is correct
16 Correct 48 ms 84004 KB Output is correct
17 Incorrect 58 ms 86684 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 83276 KB Output is correct
2 Correct 47 ms 83236 KB Output is correct
3 Correct 53 ms 83292 KB Output is correct
4 Correct 47 ms 83256 KB Output is correct
5 Correct 47 ms 83240 KB Output is correct
6 Correct 49 ms 83328 KB Output is correct
7 Correct 46 ms 83352 KB Output is correct
8 Correct 45 ms 83360 KB Output is correct
9 Correct 46 ms 83448 KB Output is correct
10 Correct 64 ms 83664 KB Output is correct
11 Correct 47 ms 83704 KB Output is correct
12 Correct 48 ms 83688 KB Output is correct
13 Correct 53 ms 83628 KB Output is correct
14 Correct 53 ms 83636 KB Output is correct
15 Correct 47 ms 83748 KB Output is correct
16 Correct 48 ms 84052 KB Output is correct
17 Incorrect 54 ms 86620 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 83260 KB Output is correct
2 Correct 46 ms 83300 KB Output is correct
3 Correct 46 ms 83316 KB Output is correct
4 Correct 46 ms 83232 KB Output is correct
5 Correct 54 ms 83296 KB Output is correct
6 Correct 46 ms 83324 KB Output is correct
7 Correct 46 ms 83308 KB Output is correct
8 Correct 46 ms 83436 KB Output is correct
9 Correct 47 ms 83404 KB Output is correct
10 Correct 53 ms 83576 KB Output is correct
11 Correct 47 ms 83684 KB Output is correct
12 Correct 47 ms 83652 KB Output is correct
13 Correct 55 ms 83796 KB Output is correct
14 Correct 47 ms 83732 KB Output is correct
15 Correct 47 ms 83660 KB Output is correct
16 Correct 52 ms 84100 KB Output is correct
17 Incorrect 52 ms 86716 KB Output isn't correct
18 Halted 0 ms 0 KB -