Submission #409327

#	Time	Username	Problem	Language	Result	Execution time	Memory
409327		victoriad	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	404 ms	262148 KiB

skyscraper

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <map>
#include <iomanip>
using namespace std;
 
int d(int x,int y,vector<vector<pair<int,int> > >&s){
  int N=s.size();
  vector<int>dis(N,1e9);
  dis[x]=0;
  priority_queue<pair<int,int> >pq;
  pq.push(make_pair(0,x));
  while(!pq.empty()){
    int nodo=pq.top().second;
    int d=-pq.top().first;
    pq.pop();
    if(d>dis[nodo])
      continue;
    dis[nodo]=d;
    for(pair<int,int>v:s[nodo]){
      int vec=v.first;
      int dv=v.second;
      if(dis[vec]>dis[nodo]+dv){
        dis[vec]=dis[nodo]+dv;
        pq.push(make_pair(-dis[vec],vec));
      }
    }
 
  }
  if(dis[y]==1e9){
    return -1;
  }
  else{
    return dis[y];
  }
}
 
int main(){
   ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N,M,B,P,x,y;
  cin>>N>>M;
  vector<vector<pair<int,int> > >s(N);
  vector<pair<int,int> >c(M);
  vector<bool>us(N,false);
  for(int i=0;i<M;i++){
  cin>>c[i].first>>c[i].second;
	us[c[i].first]=true;
  }
	for(int i=0;i<M;i++){
		B=c[i].first;
		P=c[i].second;
  		int j=B-P;
  		int o=1,u=1;
  		while(j>=0){
		if(us[j] && j!=c[0].first)
   		s[B].push_back(make_pair(j,o));
		if(j==c[1].first)break;
   		 j=j-P;
    	o++;
  		}
  		j=B+P;
  		 while(j<=N-1){
		if(us[j] && j!=c[0].first)
    	s[B].push_back(make_pair(j,u));
		if(j==c[1].first)break;
    	j=j+P;
    	u++;
  	}
	}
  
  cout<<d(c[0].first,c[1].first,s);
  return 0;
}
 

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:46:15: warning: unused variable 'x' [-Wunused-variable]
   46 |   int N,M,B,P,x,y;
      |               ^
skyscraper.cpp:46:17: warning: unused variable 'y' [-Wunused-variable]
   46 |   int N,M,B,P,x,y;
      |                 ^

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