Submission #874489

#	Time	Username	Problem	Language	Result	Execution time	Memory
874489		manizare	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	202 ms	262144 KiB

skyscraper

#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define sz(v) (int)v.size()
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 3e4 + 10 , maxq = 7e6 , sq = 176  ,mod = 1e9 + 7 , inf = 1e9 + 7, lg = 21 ;
int r[maxn][sq + 2] , dis[maxq] , mark[maxq]; ;
vector <pii> G[maxq] ;
signed main(){ 
  	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) ;
	int n , m ;cin >> n >> m ;
	int cnt = n+1 ;
	for(int i = 0 ; i < n ; i++){
		for(int j=1;j<=sq ; j++){
			G[cnt].pb({i ,0});
			r[i][j] = cnt ;
			if(i >= j){
				G[cnt].pb({r[i-j][j] , 1});
				G[r[i-j][j]].pb({cnt,1});
			}
			cnt++;
		}
	}
	int x0 , x1 ;
	for(int i = 0 ; i < m ; i++){
		int x , p ;
		cin >> x>> p ;
		if(i==0)x0 = x ;
		if(i == 1)x1 =x ;
		if(p == 0)continue ;
		if(p > sq){
			int fake = cnt ;
			cnt++;
			G[x].pb({fake , 0}) ;
			int ls =fake; 
			for(int j = x+p ; j < n ; j+=p){
				G[ls].pb({cnt , 1});
				G[cnt].pb({j,0});
				ls = cnt ;
				cnt++;
			}
			ls = fake ;
			for(int j = x-p ; j >=0 ; j-=p){
				G[ls].pb({cnt , 1});
				G[cnt].pb({j,0});
				ls = cnt ;
				cnt++;
			}
		}else{
			G[x].pb({r[x][p] , 0}); 
		}
	}
	deque <int> d ;
	for(int i = 0; i < cnt ; i++){mark[i] = 0 ;dis[i] = inf ;}
	dis[x0]= 0; 
	d.push_back(x0);
	while(d.size()){
		int v = d.front() ;d.pop_front() ;
		if(mark[v]==1)continue;
		mark[v] = 1;
		for(pii u : G[v]){
			if(dis[u.F] > dis[v]+u.S){
				dis[u.F] = dis[v] + u.S ;
				if(u.S == 1)
				d.push_back(u.F) ;
				else
				d.push_front(u.F) ;
			}
		}
	}
	if(dis[x1] == inf){
		cout << "-1\n";
	}else{
		cout << dis[x1] << "\n"; 
	}
}
/* 
 
 
*/

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:79:11: warning: 'x1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |  if(dis[x1] == inf){
      |     ~~~~~~^

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