Submission #312456

#	Time	Username	Problem	Language	Result	Execution time	Memory
312456		phathnv	Jakarta Skyscrapers (APIO15_skyscraper)	C++11	100 / 100	174 ms	97528 KiB

skyscraper

#include <bits/stdc++.h>

#define X first
#define Y second
#define mp make_pair
#define task "SKY"

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

const int N = 5e4 + 10;

int n, m, d[N];
ii a[N];
vector <int> atPos[N];

void input(){
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++)
        scanf("%d %d", &a[i].X, &a[i].Y);
}

set <int> S[N];
bool s2[2001][N];

bool mark(int b, int p){
    if (p <= 2000){
        if (s2[p][b])
            return 0;
        s2[p][b] = 1;
        return 1;
    }
    if (S[p].find(b) != S[p].end())
        return 0;
    S[p].insert(b);
    return 1;
}

iii Q[10000010];
int first = 1, last = 0;

void solve(){
    for(int i = 1; i <= m; i++)
        atPos[a[i].X].push_back(a[i].Y);

    int s = a[1].X;
    int t = a[2].X;
    memset(d, -1, sizeof(d));

    d[s] = 1;
    if (!atPos[s].empty())
        for(int i = 0; i < (int) atPos[s].size(); i++){
            int p = atPos[s][i];
            if (mark(s, p))
                Q[++last] = mp(0, mp(s, p));
        }

    while (first <= last){
        int u = Q[first].Y.X;
        int p = Q[first].Y.Y;
        int dist = Q[first].X;
        first++;

        if (u == t){
            cout << dist;
            return;
        }

        if (u - p >= 0)
            if (mark(u - p, p)){
                Q[++last] = mp(dist + 1, mp(u - p, p));
                if (d[u - p] == -1){
                    d[u - p] = 1;
                    if (!atPos[u - p].empty())
                        for(int i = 0; i < (int) atPos[u - p].size(); i++){
                            int x = atPos[u - p][i];
                            if (mark(u - p, x))
                                Q[++last] = mp(dist + 1, mp(u - p, x));
                        }
                }
            }

        if (u + p < n)
            if (mark(u + p, p)){
                Q[++last] = mp(dist + 1, mp(u + p, p));
                if (d[u + p] == -1){
                    d[u + p] = 1;
                    if (!atPos[u + p].empty())
                        for(int i = 0; i < (int) atPos[u + p].size(); i++){
                            int x = atPos[u + p][i];
                            if (mark(u + p, x))
                                Q[++last] = mp(dist + 1, mp(u + p, x));
                        }
                }
            }
    }
    cout << -1;
}

int main(){
    //freopen(task".inp", "r", stdin);
    //freopen(task".out", "w", stdout);
    input();
    solve();
}

Compilation message (stderr)

skyscraper.cpp: In function 'void input()':
skyscraper.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   21 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |         scanf("%d %d", &a[i].X, &a[i].Y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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