Submission #185666

#	Time	Username	Problem	Language	Result	Execution time	Memory
185666		dndhk	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	291 ms	71604 KiB

skyscraper

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 30000;
const int INF = 10000000;

int N, M;
vector<pii> gp[MAX_N+1];
int S, E;
vector<pii> vt;
int dist[MAX_N+1];

bool chk[MAX_N+1];

void make_graph(){
	sort(vt.begin(), vt.end());
	vt.erase(unique(vt.begin(), vt.end()), vt.end());
	int s = 0, e = 0, l;
	while(s<vt.size()){
		l = vt[s].first;
		while(e<vt.size()-1 && vt[e+1].first==l){
			e++;
		}
		for(int i=s; i<=e; i++){
			chk[vt[i].second] = true;
		}
		for(int i=s; i<=e; i++){
			int n = vt[i].second, cnt = 0;
			while(1){
				n+=l; cnt++;
				if(n>N)	break;
				//cout<<n<<" "<<vt[i].second<<" "<<cnt<<endl;
				gp[vt[i].second].pb({n, cnt});
				if(chk[n])	break;
			}
			n = vt[i].second; cnt = 0;
			while(1){
				n-=l; cnt++;
				if(n<1)	break;
				//cout<<n<<" "<<vt[i].second<<" "<<cnt<<endl;
				gp[vt[i].second].pb({n, cnt});
				if(chk[n])	break;
			}
		}
		for(int i=s; i<=e; i++){
			chk[vt[i].second] = false;
		}
		s = e+1;
		e = s;
	}
}

priority_queue<pii, vector<pii>, greater<pii> > pq;

void solve(){
	for(int i=1; i<=N; i++)	dist[i] = INF;
	dist[S] = 0;
	pq.push({0, S});
	while(!pq.empty()){
		pii now = pq.top(); pq.pop();
		if(dist[now.second]!=now.first)	continue;
		//cout<<now.second<<" "<<now.first<<endl;
		for(pii i : gp[now.second]){
			if(dist[i.first]>i.second+dist[now.second]){
				//cout<<i.first<<" "<<i.second<<" "<<dist[now.second]<<endl;
				dist[i.first] = i.second+dist[now.second];
				pq.push({dist[i.first], i.first});
			}
		}
	}
}



int main(){
	scanf("%d%d", &N, &M);
	for(int i=0; i<M; i++){
		int a, b; scanf("%d%d", &a, &b);
		a++;
		vt.pb({b, a});
		if(i==0){
			S = a;
		}else if(i==1){
			E = a;
		}
	}
	make_graph();
	solve();	
	if(dist[E]!=INF){
		printf("%d", dist[E]);
	}else{
		printf("-1");
	}
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'void make_graph()':
skyscraper.cpp:26:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(s<vt.size()){
        ~^~~~~~~~~~
skyscraper.cpp:28:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(e<vt.size()-1 && vt[e+1].first==l){
         ~^~~~~~~~~~~~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:85:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~

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