oj.uz

답안 #233294

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
233294 2020-05-20T08:46:37 Z kshitij_sodani Jakarta Skyscrapers (APIO15_skyscraper) C++17
57 / 100
 343 ms 262144 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;
int ss=180;
vector<pair<pair<int,int>,int>> adj[30001][180];//((index,power),dist)
int dist[30001][180];
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<180;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;
	//	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:69: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 93 ms 148344 KB Output is correct
2 Correct 91 ms 148332 KB Output is correct
3 Correct 92 ms 148344 KB Output is correct
4 Correct 93 ms 148344 KB Output is correct
5 Correct 96 ms 148344 KB Output is correct
6 Correct 95 ms 148344 KB Output is correct
7 Correct 91 ms 148348 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 93 ms 148344 KB Output is correct
2 Correct 91 ms 148216 KB Output is correct
3 Correct 91 ms 148344 KB Output is correct
4 Correct 92 ms 148344 KB Output is correct
5 Correct 94 ms 148344 KB Output is correct
6 Correct 96 ms 148324 KB Output is correct
7 Correct 92 ms 148344 KB Output is correct
8 Correct 94 ms 148440 KB Output is correct
9 Correct 93 ms 148600 KB Output is correct
10 Correct 91 ms 148984 KB Output is correct
11 Correct 95 ms 148984 KB Output is correct
12 Correct 92 ms 148984 KB Output is correct
13 Correct 91 ms 148984 KB Output is correct
14 Correct 98 ms 148984 KB Output is correct
15 Correct 96 ms 148988 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 148280 KB Output is correct
2 Correct 92 ms 148216 KB Output is correct
3 Correct 91 ms 148344 KB Output is correct
4 Correct 91 ms 148344 KB Output is correct
5 Correct 89 ms 148344 KB Output is correct
6 Correct 92 ms 148344 KB Output is correct
7 Correct 92 ms 148344 KB Output is correct
8 Correct 90 ms 148472 KB Output is correct
9 Correct 90 ms 148600 KB Output is correct
10 Correct 93 ms 148984 KB Output is correct
11 Correct 91 ms 148984 KB Output is correct
12 Correct 92 ms 148984 KB Output is correct
13 Correct 94 ms 148984 KB Output is correct
14 Correct 92 ms 148984 KB Output is correct
15 Correct 102 ms 149108 KB Output is correct
16 Correct 95 ms 149752 KB Output is correct
17 Correct 116 ms 155640 KB Output is correct
18 Correct 135 ms 166904 KB Output is correct
19 Correct 148 ms 169848 KB Output is correct
20 Correct 145 ms 169820 KB Output is correct
21 Correct 108 ms 151672 KB Output is correct
22 Correct 138 ms 167292 KB Output is correct
23 Correct 134 ms 165240 KB Output is correct
24 Correct 147 ms 168700 KB Output is correct
25 Correct 150 ms 169720 KB Output is correct
26 Correct 147 ms 169720 KB Output is correct
27 Correct 146 ms 169720 KB Output is correct
28 Correct 154 ms 169848 KB Output is correct
29 Correct 163 ms 169776 KB Output is correct
30 Correct 171 ms 169688 KB Output is correct
31 Correct 156 ms 169820 KB Output is correct
32 Correct 149 ms 169720 KB Output is correct
33 Correct 174 ms 169720 KB Output is correct
34 Correct 179 ms 169736 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 91 ms 148344 KB Output is correct
2 Correct 92 ms 148216 KB Output is correct
3 Correct 90 ms 148344 KB Output is correct
4 Correct 91 ms 148320 KB Output is correct
5 Correct 92 ms 148348 KB Output is correct
6 Correct 90 ms 148344 KB Output is correct
7 Correct 90 ms 148344 KB Output is correct
8 Correct 91 ms 148476 KB Output is correct
9 Correct 92 ms 148600 KB Output is correct
10 Correct 92 ms 148984 KB Output is correct
11 Correct 94 ms 149240 KB Output is correct
12 Correct 94 ms 148920 KB Output is correct
13 Correct 92 ms 148984 KB Output is correct
14 Correct 94 ms 148984 KB Output is correct
15 Correct 92 ms 148984 KB Output is correct
16 Correct 92 ms 149752 KB Output is correct
17 Correct 111 ms 155768 KB Output is correct
18 Correct 135 ms 166904 KB Output is correct
19 Correct 150 ms 169720 KB Output is correct
20 Correct 153 ms 169720 KB Output is correct
21 Correct 103 ms 151672 KB Output is correct
22 Correct 142 ms 167288 KB Output is correct
23 Correct 137 ms 165368 KB Output is correct
24 Correct 152 ms 168696 KB Output is correct
25 Correct 152 ms 169720 KB Output is correct
26 Correct 151 ms 169720 KB Output is correct
27 Correct 155 ms 169696 KB Output is correct
28 Correct 153 ms 169848 KB Output is correct
29 Correct 161 ms 169720 KB Output is correct
30 Correct 154 ms 169720 KB Output is correct
31 Correct 156 ms 169848 KB Output is correct
32 Correct 155 ms 169720 KB Output is correct
33 Correct 182 ms 169848 KB Output is correct
34 Correct 184 ms 169976 KB Output is correct
35 Correct 163 ms 164216 KB Output is correct
36 Correct 125 ms 159608 KB Output is correct
37 Correct 211 ms 170232 KB Output is correct
38 Correct 205 ms 171064 KB Output is correct
39 Correct 196 ms 171000 KB Output is correct
40 Correct 193 ms 171004 KB Output is correct
41 Correct 199 ms 171132 KB Output is correct
42 Correct 194 ms 170228 KB Output is correct
43 Correct 168 ms 170208 KB Output is correct
44 Correct 159 ms 170248 KB Output is correct
45 Correct 275 ms 172856 KB Output is correct
46 Correct 242 ms 172800 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 98 ms 148344 KB Output is correct
2 Correct 94 ms 148216 KB Output is correct
3 Correct 91 ms 148320 KB Output is correct
4 Correct 94 ms 148344 KB Output is correct
5 Correct 99 ms 148320 KB Output is correct
6 Correct 91 ms 148320 KB Output is correct
7 Correct 96 ms 148272 KB Output is correct
8 Correct 95 ms 148472 KB Output is correct
9 Correct 90 ms 148600 KB Output is correct
10 Correct 93 ms 148984 KB Output is correct
11 Correct 105 ms 148984 KB Output is correct
12 Correct 99 ms 148988 KB Output is correct
13 Correct 94 ms 148988 KB Output is correct
14 Correct 98 ms 149012 KB Output is correct
15 Correct 93 ms 148988 KB Output is correct
16 Correct 100 ms 149752 KB Output is correct
17 Correct 113 ms 155640 KB Output is correct
18 Correct 138 ms 166904 KB Output is correct
19 Correct 146 ms 169720 KB Output is correct
20 Correct 144 ms 169720 KB Output is correct
21 Correct 103 ms 151732 KB Output is correct
22 Correct 148 ms 167416 KB Output is correct
23 Correct 137 ms 165240 KB Output is correct
24 Correct 152 ms 168696 KB Output is correct
25 Correct 161 ms 169848 KB Output is correct
26 Correct 154 ms 169696 KB Output is correct
27 Correct 150 ms 169720 KB Output is correct
28 Correct 150 ms 169720 KB Output is correct
29 Correct 170 ms 169720 KB Output is correct
30 Correct 154 ms 169848 KB Output is correct
31 Correct 153 ms 169720 KB Output is correct
32 Correct 149 ms 169720 KB Output is correct
33 Correct 183 ms 169804 KB Output is correct
34 Correct 180 ms 169848 KB Output is correct
35 Correct 161 ms 164220 KB Output is correct
36 Correct 129 ms 159612 KB Output is correct
37 Correct 197 ms 170360 KB Output is correct
38 Correct 190 ms 171000 KB Output is correct
39 Correct 200 ms 171092 KB Output is correct
40 Correct 196 ms 171000 KB Output is correct
41 Correct 189 ms 171000 KB Output is correct
42 Correct 156 ms 170356 KB Output is correct
43 Correct 164 ms 170232 KB Output is correct
44 Correct 154 ms 170376 KB Output is correct
45 Correct 245 ms 172856 KB Output is correct
46 Correct 227 ms 172976 KB Output is correct
47 Runtime error 343 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
48 Halted 0 ms 0 KB -