oj.uz

Submission #233303

# Submission time Handle Problem Language Result Execution time Memory
233303 2020-05-20T08:53:52 Z kshitij_sodani Jakarta Skyscrapers (APIO15_skyscraper) C++17
22 / 100
 185 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=300;
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 148 ms 246904 KB Output is correct
2 Correct 138 ms 246904 KB Output is correct
3 Correct 140 ms 247032 KB Output is correct
4 Correct 140 ms 247012 KB Output is correct
5 Correct 143 ms 247032 KB Output is correct
6 Correct 146 ms 247032 KB Output is correct
7 Correct 143 ms 247032 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 247032 KB Output is correct
2 Correct 144 ms 246904 KB Output is correct
3 Correct 140 ms 246904 KB Output is correct
4 Correct 142 ms 247032 KB Output is correct
5 Correct 148 ms 247052 KB Output is correct
6 Correct 141 ms 247032 KB Output is correct
7 Correct 140 ms 247012 KB Output is correct
8 Correct 137 ms 247288 KB Output is correct
9 Correct 146 ms 247544 KB Output is correct
10 Correct 149 ms 247928 KB Output is correct
11 Correct 146 ms 247976 KB Output is correct
12 Correct 141 ms 247928 KB Output is correct
13 Correct 154 ms 247928 KB Output is correct
14 Correct 146 ms 248184 KB Output is correct
15 Correct 147 ms 248056 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 247032 KB Output is correct
2 Correct 140 ms 246904 KB Output is correct
3 Correct 137 ms 247032 KB Output is correct
4 Correct 147 ms 247028 KB Output is correct
5 Correct 144 ms 247032 KB Output is correct
6 Correct 140 ms 247188 KB Output is correct
7 Correct 141 ms 247020 KB Output is correct
8 Correct 141 ms 247288 KB Output is correct
9 Correct 152 ms 247420 KB Output is correct
10 Correct 147 ms 247928 KB Output is correct
11 Correct 147 ms 248060 KB Output is correct
12 Correct 146 ms 247928 KB Output is correct
13 Correct 144 ms 247928 KB Output is correct
14 Correct 148 ms 248056 KB Output is correct
15 Correct 147 ms 248056 KB Output is correct
16 Correct 145 ms 249056 KB Output is correct
17 Correct 174 ms 258168 KB Output is correct
18 Runtime error 168 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 247032 KB Output is correct
2 Correct 139 ms 246904 KB Output is correct
3 Correct 145 ms 247032 KB Output is correct
4 Correct 143 ms 247008 KB Output is correct
5 Correct 144 ms 247032 KB Output is correct
6 Correct 141 ms 247032 KB Output is correct
7 Correct 140 ms 247032 KB Output is correct
8 Correct 138 ms 247252 KB Output is correct
9 Correct 140 ms 247544 KB Output is correct
10 Correct 144 ms 247932 KB Output is correct
11 Correct 147 ms 248056 KB Output is correct
12 Correct 147 ms 247932 KB Output is correct
13 Correct 149 ms 247928 KB Output is correct
14 Correct 159 ms 248056 KB Output is correct
15 Correct 156 ms 248056 KB Output is correct
16 Correct 160 ms 249080 KB Output is correct
17 Correct 173 ms 258064 KB Output is correct
18 Runtime error 160 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 246904 KB Output is correct
2 Correct 139 ms 246904 KB Output is correct
3 Correct 165 ms 246904 KB Output is correct
4 Correct 149 ms 246904 KB Output is correct
5 Correct 148 ms 247008 KB Output is correct
6 Correct 162 ms 246956 KB Output is correct
7 Correct 150 ms 247032 KB Output is correct
8 Correct 146 ms 247272 KB Output is correct
9 Correct 146 ms 247544 KB Output is correct
10 Correct 151 ms 247928 KB Output is correct
11 Correct 172 ms 247972 KB Output is correct
12 Correct 153 ms 247956 KB Output is correct
13 Correct 150 ms 247904 KB Output is correct
14 Correct 159 ms 248056 KB Output is correct
15 Correct 185 ms 248020 KB Output is correct
16 Correct 157 ms 249080 KB Output is correct
17 Correct 182 ms 258032 KB Output is correct
18 Runtime error 171 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -