Submission #125989

#	Time	Username	Problem	Language	Result	Execution time	Memory
125989		jakob_nogler	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	10 / 100	3 ms	1080 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;

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

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]});
    }

    for(int i = 0; i < n; 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 = (id.se == doge[id.fi].size() - 1) ? n - 1 : doge[id.fi][id.se + 1];
            lo = (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});
                }

            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});
                }
        }
    }

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

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:36:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < doge[i].size(); j++)
                        ~~^~~~~~~~~~~~~~~~
skyscraper.cpp:48:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             hi = (id.se == doge[id.fi].size() - 1) ? n - 1 : doge[id.fi][id.se + 1];
                   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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