제출 #369638

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
369638		Bill_00	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	22 / 100	1090 ms	35124 KiB

skyscraper

#include <bits/stdc++.h>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define pp push
#define MOD 1000000007
#define INF 1e18
#define N 30005
#define M 5000000
typedef long long ll;
const ll c=174;

using namespace std;
ll b[N],p[N],pos[N],path[N];
bool vis[N];
set<ll>v[c][c];
int main(){
	// ios_base::sync_with_stdio(0);
	// cin.tie(0);
	// cout.tie(0)
	memset(pos,-1,sizeof(pos));
	memset(path,-1,sizeof(path));
 	ll n,m;
 	cin >> n >> m;
 	for(ll i=0;i<m;i++){
 		cin >> b[i] >> p[i];
 		pos[b[i]]=i;
 		for(ll j=1;j<c;j++){
 			v[j][b[i]%j].insert(i);
 		}
 	}
 	priority_queue<pair<ll,ll> >pq;
 	pq.push({0,0});
 	while(!pq.empty()){
 		ll cost=-pq.top().ff;
 		ll doge_id=pq.top().ss;
 		path[doge_id]=cost;
 		if(doge_id==1){
 			cout << cost;
 			return 0;
 		}
 		pq.pop();
 		vis[doge_id]=1;
 		if(p[doge_id]>=c){
 			for(ll i=b[doge_id]%p[doge_id];i<n;i+=p[doge_id]){
 				if(pos[i]!=-1){
 					if(vis[pos[i]]==0){
 						pq.push({-(cost+(abs(b[doge_id]-i))/p[doge_id]),pos[i]});
 					}
 				}
 			}
 		}
 		else{
 			for(ll i=1;i<c;i++){
 				v[i][b[doge_id]%i].erase(doge_id);
 			}
 			for(auto it=v[p[doge_id]][b[doge_id]%p[doge_id]].begin();it!=v[p[doge_id]][b[doge_id]%p[doge_id]].end();++it){
 				if(vis[*it]==0){
 					pq.push({-(cost+(abs(b[*it]-b[doge_id]))/p[doge_id]),*it});
 				}
 			}
 		}
 		while(!pq.empty() && vis[pq.top().ss]==1) pq.pop();
 	}
 	cout << path[1];
 
}

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