Submission #132816

#	Time	Username	Problem	Language	Result	Execution time	Memory
132816		MvC	Jakarta Skyscrapers (APIO15_skyscraper)	C++11	100 / 100	271 ms	79708 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;
 
bitset<P>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]][b[i]]=1;
    }
 
    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][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][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