Submission #40483

#	Time	Username	Problem	Language	Result	Execution time	Memory
40483		Waschbar	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	346 ms	92240 KiB

skyscraper

#include <bits/stdc++.h>
#define st first
#define nd second
using namespace std;

const long long INF = 1e9;
const int MOD = 1e9+7;
const int MAXN = 30000;

int n, m, strt, nd;
vector < set <int> > v(MAXN+1);
vector < vector < pair<int,int> > > g(MAXN+1);

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        if(i == 0) strt = x;
        if(i == 1) nd = x;
        v[x].insert(y);
    }


    for(int i = 0; i < n; i++){
        set <int> :: iterator it;
        for(it = v[i].begin(); it != v[i].end(); it++){
            int p = *it;
            int f = i-p;
            int pr = 1;
            while(f >= 0) {
                g[i].push_back({f,pr});
                if(v[f].count(p) != 0) break;
                f -= p;
                pr++;
            }
            f = i+p;
            pr = 1;
            while(f < n) {
                g[i].push_back({f,pr});
                if(v[f].count(p) != 0) break;
                f += p;
                pr++;
            }
        }
    }

   /* for(int i = 0; i < n; i++){
        cout << i <<" : ";
        for(int j = 0; j < g[i].size(); j++)
            cout << g[i][j].first <<"("<<g[i][j].second<<") ";
        cout << endl;
    }*/

    set < pair<int,int> > st;
    set < pair<int,int> > :: iterator it;
    vector < int > dis(n+1,INF);
    dis[strt] = 0;
    st.insert({0,strt});

    while(!st.empty()) {
        it = st.begin();
        int plz = it->second;
        dis[plz] = it->first;
        //cout << plz << " " << dis[plz] << endl;
        if(plz == nd){
            cout << dis[plz];
            return 0;
        }

        st.erase(it);

        for(int i = 0; i < g[plz].size(); i++) {
            int to = g[plz][i].first;
            int pr = g[plz][i].second;
            if(dis[to] <= dis[plz]+pr) continue;
            st.insert({dis[plz]+pr,to});
            dis[to] = dis[plz]+pr;
        }

        while(!st.empty() && dis[st.begin()->second] < st.begin()->first)
            st.erase(st.begin());

    }
	cout << -1;
}

Compilation message (stderr)

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

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