oj.uz

Submission #537210

# Submission time Handle Problem Language Result Execution time Memory
537210 2022-03-14T18:17:52 Z Gurban Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 448 ms 262144 KB 
#include "bits/stdc++.h"
using namespace std;

using ll = long long;

const int maxn=3e4+5;
const int B = 140;
int n,m;
int b[maxn],p[maxn];
int ver[maxn][B];
int dis[maxn * B];
bool vis[maxn * B];
vector<pair<int,int>>E[maxn * B];

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	int sq = min((int)sqrt(n),139);
	int sz = n - 1;
	for(int i = 0;i < n;i++) for(int j = 1;j <= sq;j++) ver[i][j] = ++sz;
	for(int i = 0;i < n;i++){
		for(int j = 1;j <= sq;j++){
			E[ver[i][j]].push_back({i,0});
			// E[i].push_back({ver[i][j],0});
			if(i - j >= 0) E[ver[i][j]].push_back({ver[i-j][j],1});
			if(i + j < n) E[ver[i][j]].push_back({ver[i+j][j],1});
		}
	}
	for(int i = 0;i < m;i++){
		cin >> b[i] >> p[i];
		if(p[i] <= sq){
			E[b[i]].push_back({ver[b[i]][p[i]],0});
			E[ver[b[i]][p[i]]].push_back({b[i],0});
		}
		else {
			for(int j = 1;b[i] - j * p[i] >= 0;j++) E[b[i]].push_back({b[i] - j * p[i],j});
			for(int j = 1;b[i] + j * p[i] < n;j++) E[b[i]].push_back({b[i] + j * p[i],j});
		}
	}

	// cout<<E[22][0].first<<' '<<E[22][0].second<<'\n';

	for(int i = 0;i <= sz;i++) dis[i] = 1e9;
	dis[b[0]] = 0;
	priority_queue<pair<int,int>>q;
	q.push({0,b[0]});
	while(!q.empty()){
		int x = q.top().second;
		q.pop();
		if(vis[x]) continue;
		vis[x] = 1;
		// cout<<x<<'\n';
		for(auto i : E[x]){
			if(dis[i.first] > dis[x] + i.second){
				dis[i.first] = dis[x] + i.second;
				q.push({-dis[i.first],i.first});
			}
		}
	}
	if(dis[b[1]] == 1e9) cout<<-1;
	else cout<<dis[b[1]];
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 98956 KB Output is correct
2 Correct 60 ms 98904 KB Output is correct
3 Correct 50 ms 98868 KB Output is correct
4 Correct 58 ms 98892 KB Output is correct
5 Correct 49 ms 98920 KB Output is correct
6 Correct 50 ms 98912 KB Output is correct
7 Correct 53 ms 98952 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 98928 KB Output is correct
2 Correct 56 ms 98956 KB Output is correct
3 Correct 50 ms 98896 KB Output is correct
4 Correct 47 ms 98976 KB Output is correct
5 Correct 55 ms 98976 KB Output is correct
6 Correct 50 ms 98908 KB Output is correct
7 Correct 54 ms 98852 KB Output is correct
8 Correct 53 ms 98892 KB Output is correct
9 Correct 58 ms 98948 KB Output is correct
10 Correct 54 ms 99020 KB Output is correct
11 Correct 57 ms 99056 KB Output is correct
12 Correct 52 ms 99168 KB Output is correct
13 Correct 51 ms 99076 KB Output is correct
14 Correct 50 ms 99156 KB Output is correct
15 Correct 55 ms 99112 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 98972 KB Output is correct
2 Correct 55 ms 98908 KB Output is correct
3 Correct 49 ms 98940 KB Output is correct
4 Correct 51 ms 98960 KB Output is correct
5 Correct 63 ms 98856 KB Output is correct
6 Correct 64 ms 98884 KB Output is correct
7 Correct 52 ms 98880 KB Output is correct
8 Correct 54 ms 98912 KB Output is correct
9 Correct 49 ms 99004 KB Output is correct
10 Correct 52 ms 99224 KB Output is correct
11 Correct 54 ms 99160 KB Output is correct
12 Correct 52 ms 99068 KB Output is correct
13 Correct 53 ms 99068 KB Output is correct
14 Correct 55 ms 99156 KB Output is correct
15 Correct 50 ms 99148 KB Output is correct
16 Correct 55 ms 99164 KB Output is correct
17 Correct 55 ms 100520 KB Output is correct
18 Correct 62 ms 103556 KB Output is correct
19 Correct 65 ms 104432 KB Output is correct
20 Correct 69 ms 104668 KB Output is correct
21 Correct 51 ms 99512 KB Output is correct
22 Correct 60 ms 103764 KB Output is correct
23 Correct 63 ms 103020 KB Output is correct
24 Correct 80 ms 104240 KB Output is correct
25 Correct 69 ms 104620 KB Output is correct
26 Correct 65 ms 104596 KB Output is correct
27 Correct 59 ms 104584 KB Output is correct
28 Correct 63 ms 104736 KB Output is correct
29 Correct 83 ms 104564 KB Output is correct
30 Correct 69 ms 104628 KB Output is correct
31 Correct 65 ms 104708 KB Output is correct
32 Correct 63 ms 104688 KB Output is correct
33 Correct 72 ms 105164 KB Output is correct
34 Correct 72 ms 105164 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 98896 KB Output is correct
2 Correct 52 ms 98892 KB Output is correct
3 Correct 47 ms 98900 KB Output is correct
4 Correct 47 ms 98888 KB Output is correct
5 Correct 56 ms 98972 KB Output is correct
6 Correct 51 ms 98860 KB Output is correct
7 Correct 53 ms 98856 KB Output is correct
8 Correct 51 ms 99000 KB Output is correct
9 Correct 48 ms 99028 KB Output is correct
10 Correct 48 ms 99100 KB Output is correct
11 Correct 53 ms 99164 KB Output is correct
12 Correct 57 ms 99068 KB Output is correct
13 Correct 53 ms 99144 KB Output is correct
14 Correct 54 ms 99076 KB Output is correct
15 Correct 60 ms 99112 KB Output is correct
16 Correct 52 ms 99248 KB Output is correct
17 Correct 54 ms 100452 KB Output is correct
18 Correct 57 ms 103572 KB Output is correct
19 Correct 63 ms 104480 KB Output is correct
20 Correct 66 ms 104588 KB Output is correct
21 Correct 56 ms 99532 KB Output is correct
22 Correct 58 ms 103748 KB Output is correct
23 Correct 59 ms 103076 KB Output is correct
24 Correct 60 ms 104264 KB Output is correct
25 Correct 76 ms 104564 KB Output is correct
26 Correct 65 ms 104652 KB Output is correct
27 Correct 63 ms 104628 KB Output is correct
28 Correct 62 ms 104728 KB Output is correct
29 Correct 67 ms 104680 KB Output is correct
30 Correct 65 ms 104608 KB Output is correct
31 Correct 76 ms 104644 KB Output is correct
32 Correct 70 ms 104780 KB Output is correct
33 Correct 71 ms 105080 KB Output is correct
34 Correct 74 ms 105100 KB Output is correct
35 Correct 69 ms 103404 KB Output is correct
36 Correct 71 ms 101452 KB Output is correct
37 Correct 82 ms 105944 KB Output is correct
38 Correct 80 ms 105940 KB Output is correct
39 Correct 79 ms 105920 KB Output is correct
40 Correct 85 ms 106044 KB Output is correct
41 Correct 88 ms 105980 KB Output is correct
42 Correct 80 ms 105516 KB Output is correct
43 Correct 65 ms 105684 KB Output is correct
44 Correct 68 ms 105540 KB Output is correct
45 Correct 86 ms 108752 KB Output is correct
46 Correct 86 ms 108720 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 98972 KB Output is correct
2 Correct 51 ms 98920 KB Output is correct
3 Correct 51 ms 98952 KB Output is correct
4 Correct 51 ms 98960 KB Output is correct
5 Correct 53 ms 98976 KB Output is correct
6 Correct 61 ms 98932 KB Output is correct
7 Correct 50 ms 98948 KB Output is correct
8 Correct 51 ms 98892 KB Output is correct
9 Correct 51 ms 99024 KB Output is correct
10 Correct 53 ms 99100 KB Output is correct
11 Correct 53 ms 99084 KB Output is correct
12 Correct 50 ms 99056 KB Output is correct
13 Correct 49 ms 99148 KB Output is correct
14 Correct 49 ms 99108 KB Output is correct
15 Correct 53 ms 99048 KB Output is correct
16 Correct 55 ms 99156 KB Output is correct
17 Correct 56 ms 100524 KB Output is correct
18 Correct 63 ms 103604 KB Output is correct
19 Correct 60 ms 104552 KB Output is correct
20 Correct 61 ms 104652 KB Output is correct
21 Correct 54 ms 99752 KB Output is correct
22 Correct 59 ms 103756 KB Output is correct
23 Correct 65 ms 103048 KB Output is correct
24 Correct 61 ms 104348 KB Output is correct
25 Correct 61 ms 104648 KB Output is correct
26 Correct 62 ms 104660 KB Output is correct
27 Correct 62 ms 104700 KB Output is correct
28 Correct 66 ms 104692 KB Output is correct
29 Correct 82 ms 104652 KB Output is correct
30 Correct 60 ms 104524 KB Output is correct
31 Correct 64 ms 104700 KB Output is correct
32 Correct 65 ms 104732 KB Output is correct
33 Correct 90 ms 105208 KB Output is correct
34 Correct 83 ms 105100 KB Output is correct
35 Correct 67 ms 103372 KB Output is correct
36 Correct 55 ms 101572 KB Output is correct
37 Correct 77 ms 105920 KB Output is correct
38 Correct 91 ms 105932 KB Output is correct
39 Correct 80 ms 105968 KB Output is correct
40 Correct 77 ms 106060 KB Output is correct
41 Correct 76 ms 106044 KB Output is correct
42 Correct 73 ms 105536 KB Output is correct
43 Correct 72 ms 105508 KB Output is correct
44 Correct 69 ms 105476 KB Output is correct
45 Correct 82 ms 108764 KB Output is correct
46 Correct 81 ms 108924 KB Output is correct
47 Correct 383 ms 181328 KB Output is correct
48 Runtime error 448 ms 262144 KB Execution killed with signal 9
49 Halted 0 ms 0 KB -