oj.uz

답안 #233301

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
233301 2020-05-20T08:51:20 Z kshitij_sodani Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 456 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=110;
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

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 90744 KB Output is correct
2 Correct 58 ms 90744 KB Output is correct
3 Correct 57 ms 90744 KB Output is correct
4 Correct 56 ms 90744 KB Output is correct
5 Correct 57 ms 90744 KB Output is correct
6 Correct 58 ms 90744 KB Output is correct
7 Correct 57 ms 90752 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 90744 KB Output is correct
2 Correct 58 ms 90744 KB Output is correct
3 Correct 56 ms 90744 KB Output is correct
4 Correct 56 ms 90744 KB Output is correct
5 Correct 56 ms 90744 KB Output is correct
6 Correct 57 ms 90748 KB Output is correct
7 Correct 57 ms 90744 KB Output is correct
8 Correct 56 ms 90876 KB Output is correct
9 Correct 58 ms 91004 KB Output is correct
10 Correct 59 ms 91140 KB Output is correct
11 Correct 66 ms 91256 KB Output is correct
12 Correct 57 ms 91128 KB Output is correct
13 Correct 58 ms 91264 KB Output is correct
14 Correct 59 ms 91256 KB Output is correct
15 Correct 62 ms 91256 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 90744 KB Output is correct
2 Correct 61 ms 90732 KB Output is correct
3 Correct 59 ms 90744 KB Output is correct
4 Correct 61 ms 90744 KB Output is correct
5 Correct 58 ms 90744 KB Output is correct
6 Correct 58 ms 90744 KB Output is correct
7 Correct 60 ms 90744 KB Output is correct
8 Correct 58 ms 90876 KB Output is correct
9 Correct 62 ms 91000 KB Output is correct
10 Correct 61 ms 91256 KB Output is correct
11 Correct 61 ms 91256 KB Output is correct
12 Correct 59 ms 91128 KB Output is correct
13 Correct 60 ms 91128 KB Output is correct
14 Correct 62 ms 91256 KB Output is correct
15 Correct 62 ms 91256 KB Output is correct
16 Correct 61 ms 91740 KB Output is correct
17 Correct 75 ms 95480 KB Output is correct
18 Correct 84 ms 102392 KB Output is correct
19 Correct 87 ms 104056 KB Output is correct
20 Correct 93 ms 104060 KB Output is correct
21 Correct 64 ms 93048 KB Output is correct
22 Correct 87 ms 102520 KB Output is correct
23 Correct 85 ms 101368 KB Output is correct
24 Correct 96 ms 103416 KB Output is correct
25 Correct 96 ms 104056 KB Output is correct
26 Correct 102 ms 104184 KB Output is correct
27 Correct 96 ms 104056 KB Output is correct
28 Correct 99 ms 104056 KB Output is correct
29 Correct 109 ms 104056 KB Output is correct
30 Correct 94 ms 104056 KB Output is correct
31 Correct 104 ms 104060 KB Output is correct
32 Correct 97 ms 104060 KB Output is correct
33 Correct 116 ms 104056 KB Output is correct
34 Correct 130 ms 104056 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 90744 KB Output is correct
2 Correct 58 ms 90744 KB Output is correct
3 Correct 55 ms 90744 KB Output is correct
4 Correct 57 ms 90744 KB Output is correct
5 Correct 57 ms 90744 KB Output is correct
6 Correct 62 ms 90744 KB Output is correct
7 Correct 58 ms 90744 KB Output is correct
8 Correct 58 ms 90872 KB Output is correct
9 Correct 63 ms 91000 KB Output is correct
10 Correct 59 ms 91128 KB Output is correct
11 Correct 62 ms 91256 KB Output is correct
12 Correct 59 ms 91212 KB Output is correct
13 Correct 61 ms 91128 KB Output is correct
14 Correct 60 ms 91256 KB Output is correct
15 Correct 63 ms 91256 KB Output is correct
16 Correct 62 ms 91768 KB Output is correct
17 Correct 76 ms 95608 KB Output is correct
18 Correct 83 ms 102264 KB Output is correct
19 Correct 90 ms 104056 KB Output is correct
20 Correct 92 ms 104056 KB Output is correct
21 Correct 66 ms 93048 KB Output is correct
22 Correct 87 ms 102520 KB Output is correct
23 Correct 87 ms 101368 KB Output is correct
24 Correct 91 ms 103416 KB Output is correct
25 Correct 92 ms 104056 KB Output is correct
26 Correct 101 ms 104144 KB Output is correct
27 Correct 104 ms 104056 KB Output is correct
28 Correct 98 ms 104056 KB Output is correct
29 Correct 107 ms 104056 KB Output is correct
30 Correct 95 ms 104056 KB Output is correct
31 Correct 99 ms 104056 KB Output is correct
32 Correct 106 ms 104056 KB Output is correct
33 Correct 114 ms 104188 KB Output is correct
34 Correct 111 ms 104160 KB Output is correct
35 Correct 123 ms 100884 KB Output is correct
36 Correct 87 ms 97912 KB Output is correct
37 Correct 144 ms 105080 KB Output is correct
38 Correct 141 ms 105208 KB Output is correct
39 Correct 143 ms 105292 KB Output is correct
40 Correct 131 ms 105312 KB Output is correct
41 Correct 140 ms 105256 KB Output is correct
42 Correct 108 ms 104412 KB Output is correct
43 Correct 106 ms 104408 KB Output is correct
44 Correct 102 ms 104432 KB Output is correct
45 Correct 171 ms 108152 KB Output is correct
46 Correct 161 ms 108156 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 90880 KB Output is correct
2 Correct 64 ms 90744 KB Output is correct
3 Correct 64 ms 90752 KB Output is correct
4 Correct 68 ms 90744 KB Output is correct
5 Correct 59 ms 90744 KB Output is correct
6 Correct 62 ms 90800 KB Output is correct
7 Correct 68 ms 90744 KB Output is correct
8 Correct 60 ms 90872 KB Output is correct
9 Correct 62 ms 91000 KB Output is correct
10 Correct 64 ms 91232 KB Output is correct
11 Correct 61 ms 91264 KB Output is correct
12 Correct 80 ms 91232 KB Output is correct
13 Correct 72 ms 91164 KB Output is correct
14 Correct 65 ms 91256 KB Output is correct
15 Correct 60 ms 91260 KB Output is correct
16 Correct 69 ms 91768 KB Output is correct
17 Correct 73 ms 95608 KB Output is correct
18 Correct 87 ms 102260 KB Output is correct
19 Correct 92 ms 104056 KB Output is correct
20 Correct 95 ms 104056 KB Output is correct
21 Correct 71 ms 93048 KB Output is correct
22 Correct 109 ms 102520 KB Output is correct
23 Correct 91 ms 101368 KB Output is correct
24 Correct 95 ms 103416 KB Output is correct
25 Correct 97 ms 104056 KB Output is correct
26 Correct 93 ms 104012 KB Output is correct
27 Correct 99 ms 104032 KB Output is correct
28 Correct 96 ms 104184 KB Output is correct
29 Correct 107 ms 104056 KB Output is correct
30 Correct 97 ms 104056 KB Output is correct
31 Correct 105 ms 104056 KB Output is correct
32 Correct 102 ms 104056 KB Output is correct
33 Correct 116 ms 104056 KB Output is correct
34 Correct 121 ms 104068 KB Output is correct
35 Correct 108 ms 100856 KB Output is correct
36 Correct 84 ms 97836 KB Output is correct
37 Correct 143 ms 104952 KB Output is correct
38 Correct 139 ms 105188 KB Output is correct
39 Correct 150 ms 105292 KB Output is correct
40 Correct 134 ms 105208 KB Output is correct
41 Correct 131 ms 105452 KB Output is correct
42 Correct 98 ms 104412 KB Output is correct
43 Correct 95 ms 104436 KB Output is correct
44 Correct 94 ms 104432 KB Output is correct
45 Correct 158 ms 108128 KB Output is correct
46 Correct 151 ms 108180 KB Output is correct
47 Correct 456 ms 181440 KB Output is correct
48 Correct 451 ms 250876 KB Output is correct
49 Runtime error 429 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
50 Halted 0 ms 0 KB -