Submission #47255

#	Time	Username	Problem	Language	Result	Execution time	Memory
47255		yusufake	Jakarta Skyscrapers (APIO15_skyscraper)	C++98	57 / 100	1087 ms	42812 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define st first
#define nd second

const int N   = 3e4 + 4;
const int kok = 177;
typedef long long ll;
typedef pair < int , int > pp;

priority_queue < pair < int , pp > > Q;
vector < int > V[N];
int H[N][kok],F[N],beg[N],jum[N],n,m,i,x,u,res;

void f(int x, int u, int t){
	if(u >= kok){
		for(int i=0;i<kok;i++){
			if(x + i*u < n && !H[x+i*u][0])
				Q.push(mp(t-i,mp(x+i*u,0)));
			if(x - i*u >= 0 && !H[x-i*u][0])
				Q.push(mp(t-i,mp(x-i*u,0)));
		}		
	}
	else if(!H[x][u]) Q.push(mp(t,mp(x,u)));
}

int main(){
	cin >> n >> m;
	for(i=0;i<m;i++){
		scanf("%d%d",&beg[i],&jum[i]);
		V[ beg[i] ].pb( jum[i] );
	}		
	
	f(beg[0],jum[0],0);
    for(; Q.size() ;){
		x = Q.top().nd.st;
		u = Q.top().nd.nd;
		res = Q.top().st;
		Q.pop();
//        cout << x << " " << u << " " << res << " ss\n";
		if(x == beg[1]) { cout << -res; return 0; }
		if(H[x][u]) continue;
        H[x][u] = 1;
		if(u){ if(x+u<n && !H[x+u][u])Q.push(mp(res-1,mp(x+u,u))); if(x-u>=0 && !H[x-u][u])Q.push(mp(res-1,mp(x-u,u))); } 
		if(F[x]) continue;
		F[x] = 1;
		for(i=0;i<V[x].size();i++)
			f(x,V[x][i],res);
 	}		
	
	cout << -1;
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:50:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0;i<V[x].size();i++)
           ~^~~~~~~~~~~~
skyscraper.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&beg[i],&jum[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43