Submission #126001

#	Time	Username	Problem	Language	Result	Execution time	Memory
126001		jakob_nogler	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	499 ms	9720 KiB

skyscraper

#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef unordered_set<int> uset;

const int inf = numeric_limits<int>::max();
const int P = 30005;

uset vis[P];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vi b(m), p(m), dist(n, inf);
    set<pii> cnt;

    vvi doge(P);
    vector<vector<pii>> pos(n);

    for(int i = 0; i < m; i++){
        cin >> b[i] >> p[i];
        if(cnt.count({b[i], p[i]})) continue;
        doge[p[i]].push_back(b[i]);
        cnt.insert({b[i], p[i]});
        vis[p[i]].insert(b[i]);
    }

    for(int i = 0; i < P; i++)
        sort(doge[i].begin(), doge[i].end());
    
    for(int i = 0; i < n; i++)
        for(int j = 0; j < doge[i].size(); j++)
            pos[doge[i][j]].push_back({i, j});

    dist[b[0]] = 0;
    set<pii> s;
    s.insert({0, b[0]});

    while(!s.empty()){
        int curr = s.begin()->se;
        s.erase(s.begin());

        for(auto id : pos[curr]){
            int hi, lo;
            hi = n - 1; // (id.se == doge[id.fi].size() - 1) ? n - 1 : doge[id.fi][id.se + 1];
            lo = 0; // (id.se == 0) ? 0 : doge[id.fi][id.se - 1];

            for(int i = curr, j = 0; i <= hi; i += id.fi, j++){
                if(dist[i] > dist[curr] + j){
                    s.erase({dist[i], i});
                    dist[i] = dist[curr] + j;
                    s.insert({dist[i], i});
                }
                if(i != curr && vis[id.fi].count(i)) break;
            }

            for(int i = curr, j = 0; i >= lo; i -= id.fi, j++){
                if(dist[i] > dist[curr] + j){
                    s.erase({dist[i], i});
                    dist[i] = dist[curr] + j;
                    s.insert({dist[i], i});
                }
                if(i != curr && vis[id.fi].count(i)) break;
            }
        }
    }

    cout << (dist[b[1]] == inf ? - 1 : dist[b[1]]) << endl;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:40:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < doge[i].size(); j++)
                        ~~^~~~~~~~~~~~~~~~

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