제출 #47260

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
47260		yusufake	Jakarta Skyscrapers (APIO15_skyscraper)	C++98	57 / 100	1104 ms	262144 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;

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

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])
				ss++, Q[t+i].pb(mp(x+i*u,0));
			if(x - i*u >= 0 && !H[x-i*u][0])
				ss++, Q[t+i].pb(mp(x-i*u,0));
		}		
	}
	else if(!H[x][u]) ss++, Q[t].pb(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(res=0 ; ss ; res++)
	for(i=0;i<Q[res].size();i++,ss--){
     	x = Q[res][i].st;
		u = Q[res][i].nd;
		if(x == beg[1]) { cout << res; return 0; }
		H[x][u] = 1;
		if(u){ if(x+u<n && !H[x+u][u])ss++,Q[res+1].pb(mp(x+u,u)); 
		if(x-u>=0 && !H[x-u][u])ss++,Q[res+1].pb(mp(x-u,u));  } 
		if(F[x]) continue;
		F[x] = 1;
		for(j=0;j<V[x].size();j++)
			f(x,V[x][j],res);
 	}		
	
	cout << -1;
	return 0;
}

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

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:39:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<Q[res].size();i++,ss--){
          ~^~~~~~~~~~~~~~
skyscraper.cpp:48:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<V[x].size();j++)
           ~^~~~~~~~~~~~
skyscraper.cpp:38:1: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 for(res=0 ; ss ; res++)
 ^~~
skyscraper.cpp:52:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  cout << -1;
  ^~~~
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