Submission #874514

#	Time	Username	Problem	Language	Result	Execution time	Memory
874514		manizare	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	697 ms	252212 KiB

skyscraper

#include <bits/stdc++.h>

#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 =3e6 + 1e5 , sq = 100  ,mod = 1e9 + 7 , inf = 1e9 + 7, lg = 21 ;
int r[maxn][sq + 1] , dis[maxq] , mark[maxq] , x[maxn]  , p[maxn] ;vector <int> vec[maxn];
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=sq;j>=1 ; 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++){
		cin >> x[i]>> p[i];
		if(i==0)x0 = x[i] ;
		if(i == 1)x1 =x[i] ;
		if(p[i] == 0)continue ;
		if(p[i] > sq){
			vec[x[i]].pb(p[i]);
		}else{
			G[x[i]].pb({r[x[i]][p[i]] , 0}); 
		}
	}
	queue <int> q ;
	for(int i = 0; i < cnt ; i++){mark[i] = 0 ;dis[i] = inf ;}
	dis[x0]= 0; 
	q.push(x0) ;
	while(q.size()){
		int v = q.front() ;q.pop() ;
		if(v < n){
			for(int z = 0 ; z < vec[v].size() ; z++){
				int u = vec[v][z] ;
				for(int j = v%u ; j < n ; j+=u){
					if(dis[j] > dis[v]+abs(v-j)/u){
						dis[j] = dis[v]+abs(v-j)/u ;
						q.push(j) ;
					}
				}
			}
		}
		mark[v] = 1;
		for(pii u : G[v]){
			if(dis[u.F] > dis[v]+u.S){
				dis[u.F] = dis[v] + u.S ;
				q.push(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:50:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |    for(int z = 0 ; z < vec[v].size() ; z++){
      |                    ~~^~~~~~~~~~~~~~~
skyscraper.cpp:68:11: warning: 'x1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |  if(dis[x1] == inf){
      |     ~~~~~~^

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