Submission #392982

#	Time	Username	Problem	Language	Result	Execution time	Memory
392982		giorgikob	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	1087 ms	3248 KiB

skyscraper

#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
using namespace std;

const int N = 3e4+5, mod = 1e9+7, sq = 500;

int n,m;
set<pair<int,int>>s;
int D[N];
int X[N],P[N];
int F[N];
vector<int>V[N];

inline void test_case(){

    cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>X[i]>>P[i];
		X[i]++;
		V[X[i]].push_back(i);
	}

	for(int i=1;i<=m;i++){
		if(i>1){
			D[i] = 1e9;
			//s.insert({1e9,i});
		}
	}

	D[1] = 0;
	F[X[1]] = 1;
	s.insert({0,1});

	while(s.size()){

		pair<int,int> p = *(s.begin());

		s.erase(s.begin());

		int i = p.second;
		int dist = p.first;
        F[X[i]] = 1;
		if(i==2){
			if(D[2]==1e9)D[2]=-1;
			cout<<D[2]<<endl;
			return ;
		}

		for(int j=X[i];j<=n;j+=P[i]){
            if(F[j] && j != X[i]) continue;
			for(int k=0;k<V[j].size();k++){

				int to = V[j][k];
				if(D[to] > dist + (j-X[i])/P[i] || D[to]==1e9){

					if(D[to]!=1e9)
					s.erase({D[to],to});
					D[to] = dist + (j-X[i])/P[i];
					s.insert({D[to],to});
				}
			}
		}

		for(int j=X[i]-P[i];j>=1;j-=P[i]){
            if(F[j]) continue;
			for(int k=0;k<V[j].size();k++){

				int to = V[j][k];
				if(D[to] > dist + (X[i]-j)/P[i] || D[to] == 1e9){

					if(D[to]!=1e9)
					s.erase({D[to],to});
					D[to] = dist + (X[i]-j)/P[i];
					s.insert({D[to],to});
				}
			}
		}
	}
	if(D[2]==1e9)
	D[2] = -1;
	cout<<D[2]<<endl;


}

 main(){
    ios::sync_with_stdio(0);

    int T = 1;
    //cin >> T;
    while(T--){
        test_case();
    }
}

Compilation message (stderr)

skyscraper.cpp: In function 'void test_case()':
skyscraper.cpp:54:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |    for(int k=0;k<V[j].size();k++){
      |                ~^~~~~~~~~~~~
skyscraper.cpp:69:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |    for(int k=0;k<V[j].size();k++){
      |                ~^~~~~~~~~~~~
skyscraper.cpp: At global scope:
skyscraper.cpp:89:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   89 |  main(){
      |       ^

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