This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 1;
const long long inf = (long long) 8e18L;
long long g[N][N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
g[i][j] = inf;
}
}
int target, start;
for (int i = 0; i < m; i++) {
int b, p;
cin >> b >> p;
if (i == 0) {
start = b;
}
if (i == 1) {
target = b;
}
for (int j = 0; j < n; j++) {
int d = abs(b - j);
if (d % p == 0) {
g[b][j] = min(g[b][j], (long long) d / p);
}
}
}
vector<long long> dist(n, inf);
priority_queue<pair<long long, int>> s;
dist[start] = 0;
s.emplace(0, start);
while (!s.empty()) {
long long exp = -s.top().first;
int u = s.top().second;
s.pop();
if (exp != dist[u]) {
continue;
}
for (int v = 0; v < n; v++) {
if (dist[u] + g[u][v] < dist[v]) {
dist[v] = dist[u] + g[u][v];
s.emplace(-dist[v], v);
}
}
}
cout << (dist[target] >= inf ? -1 : dist[target]) << '\n';
return 0;
}
Compilation message (stderr)
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:55:22: warning: 'target' may be used uninitialized in this function [-Wmaybe-uninitialized]
55 | cout << (dist[target] >= inf ? -1 : dist[target]) << '\n';
| ^
/tmp/cciHB7zA.o: In function `main':
skyscraper.cpp:(.text.startup+0x2d): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
skyscraper.cpp:(.text.startup+0x34): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
skyscraper.cpp:(.text.startup+0xde): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cin' defined in .bss._ZSt3cin section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
skyscraper.cpp:(.text.startup+0x408): relocation truncated to fit: R_X86_64_PC32 against symbol `std::cout' defined in .bss._ZSt4cout section in /usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(globals_io.o)
/tmp/cciHB7zA.o: In function `_GLOBAL__sub_I_g':
skyscraper.cpp:(.text.startup+0x4e7): relocation truncated to fit: R_X86_64_PC32 against `.bss'
skyscraper.cpp:(.text.startup+0x505): relocation truncated to fit: R_X86_64_PC32 against `.bss'
/usr/lib/gcc/x86_64-linux-gnu/9/libstdc++.a(vterminate.o): In function `__gnu_cxx::__verbose_terminate_handler()':
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x1a): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
(.text._ZN9__gnu_cxx27__verbose_terminate_handlerEv+0x27): relocation truncated to fit: R_X86_64_PC32 against `.bss._ZZN9__gnu_cxx27__verbose_terminate_handlerEvE11terminating'
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status