Submission #409700

#	Time	Username	Problem	Language	Result	Execution time	Memory
409700		victoriad	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	942 ms	52064 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;
int n,m;
int N=3e4+5;
vector<vector<pair<int,int> > >g(N);
vector<vector<int> >pos(N);

struct nodo{
	int dis,bu,po;
	nodo(int dis=0,int bu=0,int po=0):dis(dis),bu(bu),po(po){

	}
};

bool operator<(const nodo& d,const nodo& i){
	if(d.dis!=i.dis)return d.dis<i.dis;
	if(d.bu!=i.bu)return d.bu<i.bu;
	return d.po<i.po;
}

bool operator>(const nodo& d,const nodo& i){
	if(d.dis!=i.dis)return d.dis>i.dis;
	if(d.bu!=i.bu)return d.bu>i.bu;
	return d.po>i.po;
}


int solve(int raiz,vector<int>&b,vector<int>&p){

priority_queue<nodo,vector<nodo>, greater<nodo> >pq;
vector<vector<int> >dist(N);
vector<int>r(raiz+1,1e9);
for(int i=0;i<N;i++)dist[i]=r;

dist[b[0]][0]=0;
pq.push(nodo(dist[b[0]][0],b[0],0));

while(!pq.empty()){
	nodo no=pq.top();
	pq.pop();
	if(dist[no.bu][no.po]<no.dis)continue;

	//if(no.bu==b[1])return no.dis;

	if(no.po!=0){

		if(dist[no.bu][0]>no.dis){
			dist[no.bu][0]=no.dis;
			pq.push(nodo(dist[no.bu][0],no.bu,0));
		}

		if(no.bu+no.po<=n-1){
			if(dist[no.bu+no.po][no.po]>no.dis+1){
				dist[no.bu+no.po][no.po]=no.dis+1;
				pq.push(nodo(dist[no.bu+no.po][no.po],no.bu+no.po,no.po));
			}
		}

		if(no.bu-no.po>=0){
			if(dist[no.bu-no.po][no.po]>no.dis+1){
				dist[no.bu-no.po][no.po]=no.dis+1;
				pq.push(nodo(dist[no.bu-no.po][no.po],no.bu-no.po,no.po));
			}
		}
	}
	else{

		for(int i=0;i<g[no.bu].size();i++){
		if(dist[g[no.bu][i].first][0]>no.dis+g[no.bu][i].second){
			dist[g[no.bu][i].first][0]=no.dis+g[no.bu][i].second;
			pq.push(nodo(dist[g[no.bu][i].first][0],g[no.bu][i].first,0));
		}	
		}

		for(int i=0;i<pos[no.bu].size();i++){
			if(dist[no.bu][pos[no.bu][i]]>no.dis){
				dist[no.bu][pos[no.bu][i]]=no.dis;
				pq.push(nodo(dist[no.bu][pos[no.bu][i]],no.bu,pos[no.bu][i]));
			}
		}

	}
}
if(dist[b[1]][0]==1e9)return -1;
return dist[b[1]][0];

}

void todascon(int power,int inicio){
int u=power+inicio,d=1;
while(u<=n-1){
	g[inicio].push_back(make_pair(u,d));
	u+=power;
	d++;
}
u=inicio-power;
d=1;
while(u>=0){
	g[inicio].push_back(make_pair(u,d));
	u-=power;
	d++;
}
}

int main(){
  ios::sync_with_stdio(false);
   cin.tie(NULL);
	cin>>n>>m;
	vector<int>b(m);
	vector<int>p(m);

	for(int i=0;i<m;i++)cin>>b[i]>>p[i];
	
	int raiz=sqrt(3e4+5);
	for(int i=0;i<m;i++){
		if(p[i]>raiz){
			todascon(p[i],b[i]);
		}
		else{
			pos[b[i]].push_back(p[i]);
		}
	}

	cout<<solve(raiz,b,p);
	 
  return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int solve(int, std::vector<int>&, std::vector<int>&)':
skyscraper.cpp:78:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   for(int i=0;i<g[no.bu].size();i++){
      |               ~^~~~~~~~~~~~~~~~
skyscraper.cpp:85:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   for(int i=0;i<pos[no.bu].size();i++){
      |               ~^~~~~~~~~~~~~~~~~~

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