Submission #387968

#	Time	Username	Problem	Language	Result	Execution time	Memory
387968		cpp219	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	138 ms	14364 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
 
typedef long long ll;
typedef pair<ll,int> ii;
 
const int N = 3e4;
const ll INF = 1e18;
int n, m;
int b[N+2], p[N+2];
ll dis[N+2];
vector<int> adj[N+2];
unordered_map<int,bool> lf[N+2], rg[N+2];
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> b[i] >> p[i];
        adj[b[i]].push_back(p[i]);
    }
    for (int i = 0; i < n; i++) {
        sort(adj[i].begin(),adj[i].end());
        adj[i].resize(unique(adj[i].begin(),adj[i].end())-adj[i].begin());
    }
    for (int i = 0; i < n; i++) dis[i] = INF;
    priority_queue<ii,vector<ii>,greater<ii>> pq;
    pq.push({0,b[0]}); dis[b[0]] = 0;
    while (!pq.empty()) {
        ii cur = pq.top(); pq.pop();
        ll dist = cur.fi, node = cur.se;
        if (node == b[1]) {
            cout << dist << '\n';
            return 0;
        }
        if (dis[node] != dist) continue;
        for (int i : adj[node]) {
            if (!lf[node][i]) {
                for (int j = node-i, k = 1; j >= 0; j -= i, k++) {
                    ll nxDist = dist+k, nxNode = j;
                    if (dis[nxNode] > nxDist) {
                        dis[nxNode] = nxDist;
                        pq.push({nxDist,nxNode});
                    }
                    int p = lower_bound(adj[nxNode].begin(),adj[nxNode].end(),i)-adj[nxNode].begin();
                    if (p < adj[nxNode].size() && adj[nxNode][p] == i) {
                        lf[nxNode][i] = 1;
                        rg[nxNode][i] = 1;
                    }
                }
            }
            if (!rg[node][i]) {
                for (int j = node+i, k = 1; j < n; j += i, k++) {
                    ll nxDist = dist+k, nxNode = j;
                    if (dis[nxNode] > nxDist) {
                        dis[nxNode] = nxDist;
                        pq.push({nxDist,nxNode});
                    }
                    int p = lower_bound(adj[nxNode].begin(),adj[nxNode].end(),i)-adj[nxNode].begin();
                    if (p < adj[nxNode].size() && adj[nxNode][p] == i) {
                        lf[nxNode][i] = 1;
                        rg[nxNode][i] = 1;
                    }
                }
            }
        }
    }
    cout << "-1\n";
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |                     if (p < adj[nxNode].size() && adj[nxNode][p] == i) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:63:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |                     if (p < adj[nxNode].size() && adj[nxNode][p] == i) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~

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