제출 #354307

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
354307		CaroLinda	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1031 ms	3688 KiB

skyscraper

#include <bits/stdc++.h>

#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size() )

const int MAX = 30010;
const int SQ = 173 ;

using namespace std ;

int n , m ;
int b[MAX] , p[MAX] ;
vector<int> content[MAX] ;
vector<int> noName[SQ+5][SQ+5] ;

vector<int> dijkstra(int S)
{	

	vector<int> dist(n) ;
	for(int i = 0 ; i < n ; i++ ) dist[i] = MAX*MAX ;
	dist[ b[S] ] = 0 ;

	priority_queue< pii , vector<pii> , greater<pii> > fila ;
	fila.push(make_pair(0, b[S] ) ) ;

	while(!fila.empty() )
	{
		int d = fila.top().first ;
		int curr = fila.top().second ;

		fila.pop() ;

		if( d != dist[curr] ) continue ;

		for(auto e : content[curr] )
		{
			if( p[e] >= SQ )
			{
				for(int i = b[e] - p[e], w = 1 ; i >= 0 ; i-= p[e] , w++ )
					if( d + w < dist[i] )
					{
						dist[i] = d + w ;
						fila.push(make_pair(d+w, i) ) ;
					}

			  for(int i = b[e] + p[e] , w = 1 ; i < n ; i+= p[e] , w++ )
			  	if( d + w < dist[i] )
			  	{
			  		dist[i] = d + w ;
			  		fila.push(make_pair(d+w, i) ) ;
			  	} 

			}
			else 
			{
				int firstDim =  b[e] % p[e]  ;
				int secondDim = p[e] ;


				int x = lower_bound(all(noName[firstDim][secondDim]), b[e]) - noName[firstDim][secondDim].begin() ;

				int limLow = (x == 0) ? -1 : noName[firstDim][secondDim][x-1] ;
				int limUp = (x == sz(noName[firstDim][secondDim])-1 ) ? -1 : noName[firstDim][secondDim][x+1] ;

				for(int i = curr - p[e] , w = 1 ; i >= 0 ; i -= p[e] , w++ )
				{
					if(d + w < dist[i] )
					{
						dist[i] = d + w ;
						fila.push(make_pair(d+w, i) ) ;
					}
					if( i == limLow ) break ;
				}
				for(int i = b[e] + p[e] , w = 1 ; i < n  ; i += p[e] , w++ )
				{
					if(d + w < dist[i] )
					{
						dist[i] = d + w ;
						fila.push(make_pair(d+w, i) ) ;
					}

					if( i == limUp ) break ;

				}
			}
		}

	}

	return dist ;

}

int main()
{

	scanf("%d%d", &n, &m ) ;
	for(int i = 0 ; i < m ; i++ ) 
	{
		scanf("%d %d", &b[i] , &p[i] ) ;
	
		content[ b[i] ].push_back(i) ;

		if( p[i] < SQ ) noName[ b[i] % p[i] ][ p[i] ].push_back( b[i] ) ;

	}

	for(int i = 0 ; i < SQ ; i++ )
		for(int j = 0 ; j < SQ; j++ ) 
		{
			sort(all(noName[i][j]) );
			noName[i][j].erase( unique(all(noName[i][j])) , noName[i][j].end() ) ;
		}

	vector<int> dist = dijkstra(0) ;

	if(dist[ b[1] ] == MAX*MAX ) dist[ b[1] ] = -1 ;

	printf("%d\n", dist[ b[1] ] ) ;
}

컴파일 시 표준 에러 (stderr) 메시지

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |  scanf("%d%d", &n, &m ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |   scanf("%d %d", &b[i] , &p[i] ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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