oj.uz

Submission #40482

# Submission time Handle Problem Language Result Execution time Memory
40482 2018-02-02T08:35:19 Z Waschbar Jakarta Skyscrapers (APIO15_skyscraper) C++14
0 / 100
 4 ms 2760 KB 
#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());

    }

}

Compilation message

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2424 KB Output is correct
2 Correct 3 ms 2532 KB Output is correct
3 Correct 4 ms 2532 KB Output is correct
4 Incorrect 3 ms 2648 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2648 KB Output is correct
2 Correct 3 ms 2648 KB Output is correct
3 Correct 3 ms 2648 KB Output is correct
4 Incorrect 3 ms 2648 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2760 KB Output is correct
2 Correct 3 ms 2760 KB Output is correct
3 Correct 3 ms 2760 KB Output is correct
4 Incorrect 3 ms 2760 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2760 KB Output is correct
2 Correct 3 ms 2760 KB Output is correct
3 Correct 3 ms 2760 KB Output is correct
4 Incorrect 3 ms 2760 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2760 KB Output is correct
2 Correct 3 ms 2760 KB Output is correct
3 Correct 3 ms 2760 KB Output is correct
4 Incorrect 3 ms 2760 KB Output isn't correct
5 Halted 0 ms 0 KB -