제출 #409446

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

skyscraper

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <map>
#include <iomanip>
#include <stack>
#include <fstream>
using namespace std;
vector<bool>us;
 int menor(vector<vector<int> >&mov,int z,int u){
	 int n=mov.size();
	 vector<int>d(n,1e9);
	 priority_queue<pair<int,int >  >pq;
	pq.push(make_pair(0,z));
	d[z]=0;
	while(!pq.empty()){
		int t=pq.top().first;
		t*=-1;
		int nt=pq.top().second;
		if(t>=d[u])break;
		pq.pop();
		if(t>d[nt])continue;
		if(nt!=u){
		for(int c:mov[nt]){
			int x=nt+c,o=1+d[nt];
			while(x<=n-1 && o<d[u]){
				if(o<d[x]){
					d[x]=o;
					if(us[x])
					pq.push(make_pair(-d[x],x));
				}
				if(x==u)x=1e9;
				x+=c;
				o++;
			}
			int a=nt-c,l=1+d[nt];
			if(pq.top().first>=d[u])break;
			while(a>=0 && l<d[u]){
				if(l<d[a]){
					d[a]=l;
					if(us[a])
					pq.push(make_pair(-d[a],a));
				}
				if(a==u)x=-1;
				l++;
				a-=c;
			}
		if(pq.top().first>=d[u])break;
		}
		}
 
	}
	if(d[u]==1e9){
		return -1;
	}
	else{
		return d[u];
	}
 }
 
int main(){
  ios::sync_with_stdio(false);
   cin.tie(NULL);
    int n,m,a,k;
	cin>>n>>m;
	us.assign(n,false);
	vector<vector<int> >mov(n);
	vector<int>g(m);
	cin>>g[0]>>k;
	mov[g[0]].push_back(k);
	cin>>g[1]>>a;
	mov[g[1]].push_back(a);
	us[g[0]]=true;
	us[g[1]]=true;
	for(int i=2;i<m;i++){
		cin>>g[i]>>a;
		if(g[i]!=g[1]){
		mov[g[i]].push_back(a);
		us[g[i]]=true;
		}
	}
	
	cout<<menor(mov,g[0],g[1]);
	
 
    
  return 0;
}

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