Submission #108056

#	Time	Username	Problem	Language	Result	Execution time	Memory
108056		oolimry	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	642 ms	156996 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;
typedef pair<long long, int> ii;
typedef vector<ii> vii;




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];
    for(int i = 0;i < m;i++){
        cin >> doges[i].first >> doges[i].second;
    }
    //return 0;
    set<int> power[n];

    for(int i = 0;i < m;i++){
        power[doges[i].first].insert(doges[i].second);
    }
    set<ii> identical;
    vii edges[n];
    for(int i = 0;i < m;i++){
        if(identical.find(doges[i]) != identical.end()) continue;
        identical.insert(doges[i]);
        long long x = doges[i].first;
        long long p = doges[i].second;
        long long a = x + p;
        long long w = 0;
        while(a < n){
            w++;
            //cout << p << "\n";
            edges[x].push_back(ii(w,a));
            if(power[a].find(p) != power[a].end()) break;
            a += p;
        }

        a = x - p;
        w = 0;
        while(a >= 0){
            w++;
            edges[x].push_back(ii(w,a));
            if(power[a].find(p) != power[a].end()) break;
            a -= p;
        }
    }



    long long dis[n];
    fill(dis,dis+n,102345678901233ll);
    dis[doges[0].first] = 0;

    priority_queue<ii, vector<ii>, greater<ii> > pq;

    pq.push(ii(0,doges[0].first));
    while(!pq.empty()){
        ii u = pq.top();
        pq.pop();
        for(int j = 0;j < edges[u.second].size();j++){
            ii v = edges[u.second][j];
            if(dis[v.second] > v.first + u.first){
                dis[v.second] = v.first + u.first;
                pq.push(ii(dis[v.second],v.second));
            }
        }
    }
    if(dis[doges[1].first] > 10234567891ll) cout << -1;
    else cout << dis[doges[1].first];


    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:67:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < edges[u.second].size();j++){
                       ~~^~~~~~~~~~~~~~~~~~~~~~~~

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