Submission #1028580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028580		UmairAhmadMirza	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	22 / 100	1056 ms	14876 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
int const N=2005;
int const M=30005;
int const inf=1e9;
vector<pair<int,int>> adj[N];
int n,m;
int B[M],P[M];
int dist[N];
vector<int> doge[N];
int main(){
	cin>>n>>m;
	for (int i = 0; i < m; ++i){
		cin>>B[i]>>P[i];
		doge[B[i]].push_back(P[i]);
	}
	int di=0;
	for (int i = 0; i < n; ++i){
		sort(doge[i].begin(), doge[i].end());
		reverse(doge[i].begin(), doge[i].end());
		for (int j = 0; j < n; ++j)
		{
			if(i==j)
				continue;
			doge[i].push_back(-1);
			di=abs(i-j);
			for(int p=0;p<(doge[i].size())-1;p++)
				if(doge[i][p]!=doge[i][p+1] && di%doge[i][p]==0){
					adj[i].push_back({j,di/doge[i][p]});
					break;
				}
		}
	}
	for (int i = 0; i < N; ++i)
		dist[i]=inf;
	set<pair<int,int>> d;
	dist[B[0]]=0;
	d.insert({0,B[0]});
	while(d.size()){
		auto p=*(d.begin());
		int node=p.second;
		int dis=p.first;
		d.erase(d.begin());
		for(auto i:adj[node]){
			if(dist[i.first]>dis+i.second){
				dist[i.first]=dis+i.second;
				d.insert({dist[i.first],i.first});
			}
		}
	}
	if(dist[B[1]]==inf)
		dist[B[1]]=-1;
	cout<<dist[B[1]]<<endl;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:27:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |    for(int p=0;p<(doge[i].size())-1;p++)
      |                ~^~~~~~~~~~~~~~~~~~~

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