Submission #1148598

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148598		blackslex	Jakarta Skyscrapers (APIO15_skyscraper)	C++20	0 / 100	0 ms	328 KiB

skyscraper

#include<bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

int n, m;

int main() {
    scanf("%d %d", &n, &m);
    vector<vector<int>> v(n + 5, vector<int>()), v2(n + 5, vector<int>());
    vector<pii> c(m);
    for (auto &[x, y]: c) scanf("%d %d", &x, &y);
    for (int i = 0; i < m; i++) {
        auto [x, y] = c[i];
        if (i != 1) {
            for (int j = x + y; j < n; j += y) {
                v[j - y].emplace_back(j);
                v[j].emplace_back(j - y);
            }
            for (int j = x - y; j >= 0; j -= y) {
                v[j + y].emplace_back(j);
                v[j].emplace_back(j + y);
            }
        }
        if (i != 0) {
            for (int j = x + y; j < n; j += y) {
                v2[j - y].emplace_back(j);
                v2[j].emplace_back(j - y);
            }
            for (int j = x - y; j >= 0; j -= y) {
                v2[j + y].emplace_back(j);
                v2[j].emplace_back(j + y);
            }
        }
    }
    int st = c[0].first, ed = c[1].first;
    vector<int> d(n + 5, 1e9), d2(n + 5, 1e9);
    queue<int> q;
    d[st] = 0; q.emplace(st);
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (auto &e: v[cur]) {
            if (d[e] > d[cur] + 1) {
                d[e] = d[cur] + 1;
                q.emplace(e);
            }
        }
    }
    d2[ed] = 0; q.emplace(ed);
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        for (auto &e: v2[cur]) {
            if (d2[e] > d2[cur] + 1) {
                d2[e] = d2[cur] + 1;
                q.emplace(e);
            }
        }
    }
    int ans = 0;
    for (int i = 2; i < m; i++) {
        auto [x, y] = c[i];
        ans = max(ans, d[x] + d2[x]);
    }
    printf("%d", ans >= 1e9 ? -1 : ans);
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:12:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     for (auto &[x, y]: c) scanf("%d %d", &x, &y);
      |                           ~~~~~^~~~~~~~~~~~~~~~~

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