제출 #671155

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
671155		Dan4Life	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	100 / 100	206 ms	129324 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
using ll = long long;
using pii = pair<int,int>;
 
const int maxn = (int)3e4+10;
const ll LINF = (ll)1e18;
pii a[maxn];
int n, m, ans;
int dis[maxn];
bool vis[maxn];
vector<pii> adj[maxn];
vector<int> doge[maxn];

void dijkstra(int s){
	fill(dis,dis+maxn,LINF); fill(vis, vis+maxn,false);
	priority_queue<pii,vector<pii>,greater<pii>> pq;
	pq.push({0,s}); dis[s]=0;
	while(!pq.empty()){
		int a = pq.top().se; pq.pop();
		if(vis[a]) continue; vis[a]=1;
		for(auto u : adj[a]){
			int b = u.fi, w = u.se;
			if(dis[a]+w<dis[b]){
				dis[b]=dis[a]+w;
				pq.push({dis[b],b});
			}
		}
	}
}

int32_t main() {
	cin >> n >> m; ans = LINF;
	for(int i = 0; i < m; i++) cin >> a[i].fi >> a[i].se, doge[a[i].fi].pb(a[i].se);
	for(int i = 0; i < n; i++)
		sort(all(doge[i])), doge[i].erase(unique(all(doge[i])), doge[i].end());
	for(int i = 0; i < n; i++){
		for(auto p : doge[i]){
			for(int j = 1; ;j++){
				int b = i+j*p; if(b>=n) break;
				auto itr = lower_bound(doge[b].begin(), doge[b].end(), p)-doge[b].begin();
				adj[i].pb({b,j});if(itr!=doge[b].size() and doge[b][itr]==p) break;
			}
			for(int j = -1; ; j--){
				int b = i+j*p; if(b<0) break;
				auto itr = lower_bound(doge[b].begin(), doge[b].end(), p)-doge[b].begin();
				adj[i].pb({b,-j}); if(itr!=doge[b].size() and doge[b][itr]==p) break;
			}
		}
	}
	dijkstra(a[0].fi); cout << (dis[a[1].fi]==LINF?-1:dis[a[1].fi]);
}

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

skyscraper.cpp: In function 'void dijkstra(long long int)':
skyscraper.cpp:26:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   26 |   if(vis[a]) continue; vis[a]=1;
      |   ^~
skyscraper.cpp:26:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   26 |   if(vis[a]) continue; vis[a]=1;
      |                        ^~~
skyscraper.cpp: In function 'int32_t main()':
skyscraper.cpp:47:28: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     adj[i].pb({b,j});if(itr!=doge[b].size() and doge[b][itr]==p) break;
      |                         ~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:52:30: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     adj[i].pb({b,-j}); if(itr!=doge[b].size() and doge[b][itr]==p) break;
      |                           ~~~^~~~~~~~~~~~~~~~

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