oj.uz

Submission #233304

# Submission time Handle Problem Language Result Execution time Memory
233304 2020-05-20T08:54:08 Z kshitij_sodani Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 311 ms 262148 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
int n,m;
int aa,bb;
const int ss=200;
vector<pair<pair<int,int>,int>> adj[30001][ss];//((index,power),dist)
int dist[30001][ss];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	int st;
	int endd;
	memset(dist,-1,sizeof(dist));
	for(int j=0;j<m;j++){
		cin>>aa>>bb;
		if(j==0){
			st=aa;
		}
		if(j==1){
			endd=aa;
		}
		if(bb>=ss){
			for(int i=aa+bb;i<n;i+=bb){
				adj[aa][0].pb({{i,0},(i-aa)/bb});
			}
			for(int i=aa-bb;i>=0;i-=bb){
				adj[aa][0].pb({{i,0},(aa-i)/bb});
			}
		}
		else{
			adj[aa][0].pb({{aa,bb},0});
		//	adj[aa][bb].pb({{aa,0},0});
		}
	}
	for(int i=0;i<n;i++){
		for(int j=1;j<ss;j++){
			if(i+j<n){
				adj[i][j].pb({{i+j,j},1});
			}
			if(i-j>=0 and i-j<n){
				adj[i][j].pb({{i-j,j},1});
			}
			adj[i][j].pb({{i,0},0});

		}
	}
	priority_queue<pair<int,pair<int,int>>> ac;
	ac.push({0,{st,0}});
	dist[st][0]=0;
	while(ac.size()){
		pair<int,pair<int,int>> no=ac.top();
		ac.pop();
		no.a=-no.a;
		if(dist[no.b.a][no.b.b]<no.a){
			continue;
		}
	//	cout<<no.b.a<<","<<no.b.b<<","<<no.a<<endl;
		for(auto j:adj[no.b.a][no.b.b]){
			if(dist[j.a.a][j.a.b]==-1 or dist[j.a.a][j.a.b]>dist[no.b.a][no.b.b]+j.b){
				dist[j.a.a][j.a.b]=dist[no.b.a][no.b.b]+j.b;
				ac.push({-dist[j.a.a][j.a.b],{j.a}});
			}
		}
	}
	cout<<dist[endd][0]<<endl;








	return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:56:13: warning: 'st' may be used uninitialized in this function [-Wmaybe-uninitialized]
  dist[st][0]=0;
  ~~~~~~~~~~~^~
skyscraper.cpp:72:20: warning: 'endd' may be used uninitialized in this function [-Wmaybe-uninitialized]
  cout<<dist[endd][0]<<endl;
                    ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 164728 KB Output is correct
2 Correct 107 ms 164728 KB Output is correct
3 Correct 164 ms 164728 KB Output is correct
4 Correct 112 ms 164728 KB Output is correct
5 Correct 103 ms 164728 KB Output is correct
6 Correct 106 ms 164856 KB Output is correct
7 Correct 101 ms 164728 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 164728 KB Output is correct
2 Correct 107 ms 164728 KB Output is correct
3 Correct 112 ms 164728 KB Output is correct
4 Correct 107 ms 164836 KB Output is correct
5 Correct 126 ms 164728 KB Output is correct
6 Correct 109 ms 164812 KB Output is correct
7 Correct 107 ms 164832 KB Output is correct
8 Correct 107 ms 164920 KB Output is correct
9 Correct 101 ms 165112 KB Output is correct
10 Correct 104 ms 165368 KB Output is correct
11 Correct 104 ms 165472 KB Output is correct
12 Correct 103 ms 165496 KB Output is correct
13 Correct 101 ms 165496 KB Output is correct
14 Correct 104 ms 165496 KB Output is correct
15 Correct 102 ms 165496 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 164728 KB Output is correct
2 Correct 101 ms 164712 KB Output is correct
3 Correct 104 ms 164728 KB Output is correct
4 Correct 100 ms 164728 KB Output is correct
5 Correct 103 ms 164856 KB Output is correct
6 Correct 102 ms 164856 KB Output is correct
7 Correct 101 ms 164856 KB Output is correct
8 Correct 100 ms 164984 KB Output is correct
9 Correct 101 ms 165112 KB Output is correct
10 Correct 100 ms 165496 KB Output is correct
11 Correct 105 ms 165496 KB Output is correct
12 Correct 100 ms 165496 KB Output is correct
13 Correct 102 ms 165496 KB Output is correct
14 Correct 105 ms 165496 KB Output is correct
15 Correct 108 ms 165600 KB Output is correct
16 Correct 102 ms 166264 KB Output is correct
17 Correct 134 ms 172796 KB Output is correct
18 Correct 153 ms 185208 KB Output is correct
19 Correct 161 ms 188536 KB Output is correct
20 Correct 158 ms 188476 KB Output is correct
21 Correct 108 ms 168312 KB Output is correct
22 Correct 150 ms 185720 KB Output is correct
23 Correct 155 ms 183544 KB Output is correct
24 Correct 156 ms 187240 KB Output is correct
25 Correct 156 ms 188412 KB Output is correct
26 Correct 159 ms 188408 KB Output is correct
27 Correct 156 ms 188536 KB Output is correct
28 Correct 162 ms 188412 KB Output is correct
29 Correct 172 ms 188412 KB Output is correct
30 Correct 165 ms 188408 KB Output is correct
31 Correct 167 ms 188412 KB Output is correct
32 Correct 164 ms 188424 KB Output is correct
33 Correct 188 ms 188536 KB Output is correct
34 Correct 195 ms 188536 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 164728 KB Output is correct
2 Correct 103 ms 164728 KB Output is correct
3 Correct 102 ms 164728 KB Output is correct
4 Correct 100 ms 164728 KB Output is correct
5 Correct 102 ms 164856 KB Output is correct
6 Correct 101 ms 164856 KB Output is correct
7 Correct 99 ms 164856 KB Output is correct
8 Correct 102 ms 164984 KB Output is correct
9 Correct 100 ms 165112 KB Output is correct
10 Correct 105 ms 165372 KB Output is correct
11 Correct 107 ms 165496 KB Output is correct
12 Correct 105 ms 165500 KB Output is correct
13 Correct 109 ms 165496 KB Output is correct
14 Correct 100 ms 165496 KB Output is correct
15 Correct 105 ms 165496 KB Output is correct
16 Correct 106 ms 166264 KB Output is correct
17 Correct 133 ms 172792 KB Output is correct
18 Correct 157 ms 185340 KB Output is correct
19 Correct 156 ms 188408 KB Output is correct
20 Correct 166 ms 188408 KB Output is correct
21 Correct 117 ms 168392 KB Output is correct
22 Correct 165 ms 185720 KB Output is correct
23 Correct 150 ms 183416 KB Output is correct
24 Correct 160 ms 187256 KB Output is correct
25 Correct 159 ms 188536 KB Output is correct
26 Correct 160 ms 188408 KB Output is correct
27 Correct 158 ms 188408 KB Output is correct
28 Correct 161 ms 188412 KB Output is correct
29 Correct 185 ms 188520 KB Output is correct
30 Correct 161 ms 188376 KB Output is correct
31 Correct 161 ms 188408 KB Output is correct
32 Correct 168 ms 188356 KB Output is correct
33 Correct 187 ms 188408 KB Output is correct
34 Correct 192 ms 188536 KB Output is correct
35 Correct 173 ms 181980 KB Output is correct
36 Correct 134 ms 177272 KB Output is correct
37 Correct 209 ms 188668 KB Output is correct
38 Correct 213 ms 189304 KB Output is correct
39 Correct 213 ms 189436 KB Output is correct
40 Correct 207 ms 189432 KB Output is correct
41 Correct 203 ms 189432 KB Output is correct
42 Correct 165 ms 188788 KB Output is correct
43 Correct 163 ms 188788 KB Output is correct
44 Correct 161 ms 188808 KB Output is correct
45 Correct 262 ms 190776 KB Output is correct
46 Correct 249 ms 190520 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 164728 KB Output is correct
2 Correct 99 ms 164708 KB Output is correct
3 Correct 104 ms 164824 KB Output is correct
4 Correct 100 ms 164728 KB Output is correct
5 Correct 99 ms 164856 KB Output is correct
6 Correct 101 ms 164728 KB Output is correct
7 Correct 103 ms 164888 KB Output is correct
8 Correct 101 ms 164984 KB Output is correct
9 Correct 103 ms 165112 KB Output is correct
10 Correct 101 ms 165368 KB Output is correct
11 Correct 102 ms 165496 KB Output is correct
12 Correct 100 ms 165624 KB Output is correct
13 Correct 103 ms 165496 KB Output is correct
14 Correct 102 ms 165496 KB Output is correct
15 Correct 106 ms 165496 KB Output is correct
16 Correct 103 ms 166264 KB Output is correct
17 Correct 124 ms 172920 KB Output is correct
18 Correct 162 ms 185340 KB Output is correct
19 Correct 156 ms 188408 KB Output is correct
20 Correct 161 ms 188536 KB Output is correct
21 Correct 110 ms 168308 KB Output is correct
22 Correct 150 ms 185720 KB Output is correct
23 Correct 149 ms 183440 KB Output is correct
24 Correct 159 ms 187256 KB Output is correct
25 Correct 160 ms 188408 KB Output is correct
26 Correct 159 ms 188364 KB Output is correct
27 Correct 159 ms 188408 KB Output is correct
28 Correct 170 ms 188408 KB Output is correct
29 Correct 175 ms 188408 KB Output is correct
30 Correct 164 ms 188408 KB Output is correct
31 Correct 163 ms 188536 KB Output is correct
32 Correct 162 ms 188408 KB Output is correct
33 Correct 184 ms 188468 KB Output is correct
34 Correct 180 ms 188408 KB Output is correct
35 Correct 168 ms 182088 KB Output is correct
36 Correct 136 ms 177144 KB Output is correct
37 Correct 211 ms 188664 KB Output is correct
38 Correct 209 ms 189388 KB Output is correct
39 Correct 209 ms 189432 KB Output is correct
40 Correct 206 ms 189432 KB Output is correct
41 Correct 206 ms 189432 KB Output is correct
42 Correct 164 ms 188788 KB Output is correct
43 Correct 164 ms 188788 KB Output is correct
44 Correct 163 ms 188808 KB Output is correct
45 Correct 254 ms 190776 KB Output is correct
46 Correct 258 ms 190392 KB Output is correct
47 Runtime error 311 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Halted 0 ms 0 KB -