Submission #1264181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264181		elotelo966	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	57 / 100	1097 ms	79360 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define OYY LLONG_MAX
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define pb push_back
#define lim 200005

int n,m;

int dizi[lim][2];

set<int> st[lim];

vector<pair<int,int>> v[lim];

int vis[lim],dist[lim];

inline void dij(int bas){
	for(int i=1;i<=n;i++){
		vis[i]=0;
		dist[i]=LLONG_MAX;
	}
	dist[bas]=0;
	priority_queue<pair<int,int>> pq;
	pq.push({0,bas});
	while(pq.size()){
		int node=pq.top().se;
		pq.pop();
		if(vis[node])continue;
		vis[node]=1;
		for(auto go:v[node]){
			if(dist[node]!=LLONG_MAX && dist[go.fi]>dist[node]+go.se){
				dist[go.fi]=dist[node]+go.se;
				pq.push({-dist[go.fi],go.fi});
			}
		}
	}
}

int32_t main(){
	faster
	cin>>n>>m;
	
	int sta,tar;
	
	for(int i=1;i<=m;i++){
		cin>>dizi[i][0]>>dizi[i][1];
		dizi[i][0]++;
		st[dizi[i][0]].insert(dizi[i][1]);
		if(i==1)sta=dizi[i][0];
		else if(i==2)tar=dizi[i][0];
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j)continue;
			int tut=abs(i-j);
			for(int k=1;k*k<=tut;k++){
				if(tut%k==0){
					int a=k;
					int b=tut/k;
					//cout<<i<<" "<<j<<" "<<a<<" "<<b<<" "<<tut<<" "<<st[i].count(a)<<endl;
					if(st[i].count(a)){
						v[i].pb({j,b});
					}
					if(a!=b){
						if(st[i].count(b)){
							v[i].pb({j,a});
						}
					}
				}
			}
		}
	}
	
	//~ FOR{
		//~ cout<<v[i].size()<<endl;
		//~ for(auto a:v[i])cout<<a.fi<<" "<<a.se<<endl;
	//~ }
	
	dij(sta);
	
	//~ FOR{
		//~ cout<<dist[i]<<" ";
	//~ }
	
	int cev=dist[tar];
	if(cev==LLONG_MAX)cev=-1;
	
	cout<<cev<<'\n';
	
	return 0;
}

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