Submission #108054

#	Time	Username	Problem	Language	Result	Execution time	Memory
108054		oolimry	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	36 / 100	417 ms	263168 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;
typedef pair<long long, long long> 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);
    }

    vii edges[n];
    for(int i = 0;i < m;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;
        }
    }

    for(int i = 0;i < n;i++){
        for(int j = 0;j < edges[i].size();j++){
            ii v = edges[i][j];
            //cout << v.second << " " << v.first << "|";
        }
        //cout << "\n";
    }

    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:54:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0;j < edges[i].size();j++){
                       ~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:55:16: warning: variable 'v' set but not used [-Wunused-but-set-variable]
             ii v = edges[i][j];
                ^
skyscraper.cpp:71: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: 0 / 21
• Subtask 5: 0 / 43