Submission #108045

#	Time	Username	Problem	Language	Result	Execution time	Memory
108045		oolimry	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	1075 ms	8056 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;
typedef pair<long long, long long> ii;





int main()
{
    //freopen("i.txt","r",stdin);
    long long n, m;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;

    ii doges[m];

    vector<long long> posDog[n];

    for(int i = 0;i < m;i++){
        cin >> doges[i].first >> doges[i].second;
        if(doges[i].first - doges[i].second >= 0 || doges[i].first + doges[i].second < n) posDog[doges[i].first].push_back(i);
    }



    bool touched[n];
    fill(touched,touched+n,false);
    deque<ii> bfs;
    map<ii, long long> vis;

    bfs.push_back(doges[0]);
    vis[doges[0]] = 0ll;
    //cout << (ii(1,0) == ii(1,0));
    int kk = 0;
    while(!bfs.empty()){
        ii u = bfs.front();
        bfs.pop_front();
        long long x = u.first;
        long long p = u.second;
        //cout << x << " " << p << " " << vis[u] << "\n";

        if(x == doges[1].first){
            cout << vis[u];
            return 0;
        }

        if(!touched[x]){
            for(int i = 0;i < posDog[x].size();i++){

                ii v = doges[posDog[x][i]];
                if(v == u) continue;
                if(vis.find(v) == vis.end()){
                    vis[v] = vis[u];
                    bfs.push_front(v);
                }
                else if(vis[v] > vis[u]){
                    vis[v] = vis[u];
                    bfs.push_front(v);
                }
            }
            //touched[x] = true;
        }

        //if(kk > 300000) return 1;

        if(x - p >= 0){
            ii v = ii(x-p,p);
            if(vis.find(v) == vis.end()){
                vis[v] = vis[u] + 1;
                bfs.push_back(v);
                kk++;
            }
            else{
                if(vis[v] > vis[u] + 1){
                    vis[v] = vis[u] + 1;
                    bfs.push_back(v);
                    kk++;
                }
            }
        }
        if(x + p < n){
            ii v = ii(x+p,p);
            if(vis.find(v) == vis.end()){
                vis[v] = vis[u] + 1;
                bfs.push_back(v);
                kk++;
            }
            else{
                if(vis[v] > vis[u] + 1){
                    vis[v] = vis[u] + 1;
                    bfs.push_back(v);
                    kk++;
                }
            }
        }
    }

    cout << -1;
    return 0;

    //for(map<ii, long long>::iterator it = vis.begin();it != vis.end();it++){
    //    cout << it->first.first << " " << it->first.second << " " << it->second << "\n";
    //}








    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:51:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0;i < posDog[x].size();i++){
                           ~~^~~~~~~~~~~~~~~~~~

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