Submission #786151

#	Time	Username	Problem	Language	Result	Execution time	Memory
786151		devariaota	Jakarta Skyscrapers (APIO15_skyscraper)	C++17	0 / 100	1 ms	980 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define endl "\n"
#define pii pair<ll,ll>
#define pb push_back
#define vi vector<ll>
#define pque priority_queue
#define pqueg priority_queue<ll,vector<ll>,greater<ll>>
#define que queue<ll>
#define FOR(m,i,n) for(int i=(m); i<=(n); i++)
#define FORM(m,i,n) for(int i=(m); i>=(n); i--)
ll n,m;
pii a[30300];
vector<pii> adj[30300];
priority_queue<pii,vector<pii>,greater<pii>> pq;
ll dist[30030];
bool vis[30030];
ll temp;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  FOR(1,i,m) {
    cin >> a[i].fi >> a[i].se;
    if(i == 2) {
      temp = a[i].fi;
    }
  }
  sort(a+1,a+m+1);
  FOR(1,i,m) {
    FOR(1,j,m) {
      if(a[i].fi == a[j].fi) continue;
      if(abs(a[i].fi - a[j].fi) % a[i].se == 0) {
        adj[a[i].fi].pb({a[j].fi,abs(a[i].fi - a[j].fi) / a[i].se});
      }
    }
  }
  pq.push({0,a[1].fi});
  FOR(1,i,n) {
    dist[i] = 1e9;
  }
  while(!pq.empty()) {
    pii x = pq.top();
    pq.pop();
    for(auto i : adj[x.se]) {
//      if(!vis[i.fi]) {
//        vis[i.fi] = true;
        if(dist[i.fi] > dist[x.se] + i.se) {
          dist[i.fi] = dist[x.se] + i.se;
          pq.push({dist[i.fi],i.fi});
        }
//      }
    }
  }
  if(dist[temp] == 1e9) {
    cout << -1 << endl;
  }
  else {
    cout << dist[1] << endl;
  }
}

/*
5 3
0 2
1 1  
4 1

5 3
0 2 
1 3
2 2
*/

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