This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// CF template, version 3.0
#include <bits/stdc++.h>
using namespace std;
#define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0)
#define getTest int t; cin >> t
#define eachTest for (int _var=0;_var<t;_var++)
#define get(name) int (name); cin >> (name)
#define out(o) cout << (o)
#define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
#define sortl(name) sort((name).begin(), (name).end())
#define rev(name) reverse((name).begin(), (name).end())
#define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
#define decision(b) if (b){out("YES");}else{out("NO");}
#define int long long int
signed main() {
improvePerformance;
get(n);
get(m);
vector<pair<int, int>> doges;
vector<vector<bool>> has(n, vector<bool>(n + 1, false));
vector<bool> one(n, false);
vector<vector<int>> div(n + 1);
for (int d = 1; d <= n; d++) {
for (int j = d; j <= n; j += d) {
div[j].push_back(d);
}
}
forto(m, i) {
get(b);
get(p);
doges.push_back({b, p});
has[b][p] = true;
one[b] = true;
}
vector<vector<pair<int, int>>> adjList(n);
forto(n, i) {
forto(n, j) {
if (i == j) continue;
if (!one[j]) continue;
int maxdiv = -1;
int dist = abs(j - i);
for (int divisor: div[dist]) {
if (has[i][divisor]) maxdiv = divisor;
}
if (maxdiv != -1) adjList[i].push_back({j, dist / maxdiv});
}
}
vector<int> shortest(n, 1e18);
vector<bool> visited(n, false);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
int start = doges[0].first;
pq.push({0, start});
while (!pq.empty()) {
auto top = pq.top();
int dist = top.first;
int node = top.second;
pq.pop();
if (visited[node]) continue;
visited[node] = true;
shortest[node] = min(shortest[node], dist);
for (auto con: adjList[node]) {
int dest = con.first;
int weight = con.second;
if (!visited[dest]) pq.push({shortest[node] + weight, dest});
}
}
int pos = doges[1].first;
if (shortest[pos] == 1e18) out(-1);
else out(shortest[pos]);
}
Compilation message (stderr)
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:10:23: warning: unnecessary parentheses in declaration of 'n' [-Wparentheses]
10 | #define get(name) int (name); cin >> (name)
| ^
skyscraper.cpp:23:5: note: in expansion of macro 'get'
23 | get(n);
| ^~~
skyscraper.cpp:10:23: warning: unnecessary parentheses in declaration of 'm' [-Wparentheses]
10 | #define get(name) int (name); cin >> (name)
| ^
skyscraper.cpp:24:5: note: in expansion of macro 'get'
24 | get(m);
| ^~~
skyscraper.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
| ^
skyscraper.cpp:34:5: note: in expansion of macro 'forto'
34 | forto(m, i) {
| ^~~~~
skyscraper.cpp:10:23: warning: unnecessary parentheses in declaration of 'b' [-Wparentheses]
10 | #define get(name) int (name); cin >> (name)
| ^
skyscraper.cpp:35:9: note: in expansion of macro 'get'
35 | get(b);
| ^~~
skyscraper.cpp:10:23: warning: unnecessary parentheses in declaration of 'p' [-Wparentheses]
10 | #define get(name) int (name); cin >> (name)
| ^
skyscraper.cpp:36:9: note: in expansion of macro 'get'
36 | get(p);
| ^~~
skyscraper.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
| ^
skyscraper.cpp:42:5: note: in expansion of macro 'forto'
42 | forto(n, i) {
| ^~~~~
skyscraper.cpp:15:35: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
| ^
skyscraper.cpp:43:9: note: in expansion of macro 'forto'
43 | forto(n, j) {
| ^~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |