Submission #158241

#	Time	Username	Problem	Language	Result	Execution time	Memory
158241		Akashi	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	100 / 100	260 ms	65636 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

int sgn[] = {-1, 1};
int n, m, pos;
int d[30005];
bool viz[30005];
set <int> s[30005];
vector <pair <int, int> > v[30005];
priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > q;

int main()
{
    scanf("%d%d", &n, &m);

    int x2, x, y;
    scanf("%d%d", &x, &y);
    s[x].insert(y); x2 = x;
    scanf("%d%d", &x, &y);
    pos = x;

    if(pos == x2){
        printf("0");
        return 0;
    }

    for(int i = 3; i <= m ; ++i){
        scanf("%d%d", &x, &y);
        s[x].insert(y);
    }

    for(int i = 0; i < n ; ++i){
        d[i] = 1e9;
        if(s[i].empty()) continue ;

        for(auto it : s[i]){
            int nod = i, x = i, y = it, k = 1;
            while(x + y < n){
                v[nod].push_back({x + y, k});

                x += y; ++k;
                if(s[x].find(y) != s[x].end()) break ;
            }

            x = i; k = 1;
            while(x - y >= 0){
                v[nod].push_back({x - y, k});

                x -= y; ++k;
                if(s[x].find(y) != s[x].end()) break ;
            }
        }
    }

    q.push({0, x2});
    d[x2] = 0;
    while(!q.empty()){
        int l = q.top().first, nod = q.top().second;
        if(pos == nod){
            printf("%d", l);
            return 0;
        }

        q.pop();
        if(viz[nod]) continue ;
        viz[nod] = 1;

        for(auto it : v[nod]){
            if(d[it.first] > l + it.second){
                d[it.first] = l + it.second;
                q.push({l + it.second, it.first});
            }
        }
    }

    printf("-1");

    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &x, &y);
     ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &x, &y);
     ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~

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