// 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;
forto(m, i) {
get(b);
get(p);
doges.push_back({b, p});
}
vector<vector<pair<int, int>>> adjList(m);
forto(m, i) {
forto(m, j) {
if (i == j) continue;
int dist = abs(doges[j].first - doges[i].first);
int jump = doges[i].second;
if (dist % jump == 0) adjList[i].push_back({j, dist / jump});
}
}
vector<int> shortest(m, 1e18);
vector<bool> visited(m, false);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, 0});
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});
}
}
if (shortest[1] == 1e18) out(-1);
else out(shortest[1]);
}
Compilation message
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:26:5: note: in expansion of macro 'forto'
26 | 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:27:9: note: in expansion of macro 'get'
27 | get(b);
| ^~~
skyscraper.cpp:10:23: warning: unnecessary parentheses in declaration of 'p' [-Wparentheses]
10 | #define get(name) int (name); cin >> (name)
| ^
skyscraper.cpp:28:9: note: in expansion of macro 'get'
28 | 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:32:5: note: in expansion of macro 'forto'
32 | forto(m, 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:33:9: note: in expansion of macro 'forto'
33 | forto(m, j) {
| ^~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
324 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
320 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
316 KB |
Output is correct |
10 |
Correct |
2 ms |
580 KB |
Output is correct |
11 |
Correct |
36 ms |
6724 KB |
Output is correct |
12 |
Correct |
393 ms |
80672 KB |
Output is correct |
13 |
Correct |
387 ms |
81216 KB |
Output is correct |
14 |
Correct |
29 ms |
4276 KB |
Output is correct |
15 |
Correct |
29 ms |
4304 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
2 ms |
596 KB |
Output is correct |
11 |
Correct |
36 ms |
6720 KB |
Output is correct |
12 |
Correct |
389 ms |
80708 KB |
Output is correct |
13 |
Correct |
408 ms |
81136 KB |
Output is correct |
14 |
Correct |
29 ms |
4288 KB |
Output is correct |
15 |
Correct |
29 ms |
4296 KB |
Output is correct |
16 |
Correct |
4 ms |
836 KB |
Output is correct |
17 |
Correct |
20 ms |
2272 KB |
Output is correct |
18 |
Correct |
5 ms |
468 KB |
Output is correct |
19 |
Correct |
2 ms |
340 KB |
Output is correct |
20 |
Correct |
451 ms |
81084 KB |
Output is correct |
21 |
Correct |
7 ms |
468 KB |
Output is correct |
22 |
Correct |
3 ms |
328 KB |
Output is correct |
23 |
Correct |
5 ms |
468 KB |
Output is correct |
24 |
Correct |
17 ms |
852 KB |
Output is correct |
25 |
Correct |
19 ms |
796 KB |
Output is correct |
26 |
Correct |
325 ms |
75160 KB |
Output is correct |
27 |
Correct |
343 ms |
76860 KB |
Output is correct |
28 |
Correct |
17 ms |
896 KB |
Output is correct |
29 |
Correct |
4 ms |
980 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
3 ms |
468 KB |
Output is correct |
32 |
Correct |
2 ms |
468 KB |
Output is correct |
33 |
Correct |
29 ms |
4292 KB |
Output is correct |
34 |
Correct |
29 ms |
4308 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
224 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
2 ms |
596 KB |
Output is correct |
11 |
Correct |
36 ms |
6740 KB |
Output is correct |
12 |
Correct |
399 ms |
80704 KB |
Output is correct |
13 |
Correct |
399 ms |
81104 KB |
Output is correct |
14 |
Correct |
29 ms |
4212 KB |
Output is correct |
15 |
Correct |
29 ms |
4244 KB |
Output is correct |
16 |
Correct |
4 ms |
852 KB |
Output is correct |
17 |
Correct |
21 ms |
2204 KB |
Output is correct |
18 |
Correct |
5 ms |
448 KB |
Output is correct |
19 |
Correct |
2 ms |
340 KB |
Output is correct |
20 |
Correct |
442 ms |
81152 KB |
Output is correct |
21 |
Correct |
7 ms |
468 KB |
Output is correct |
22 |
Correct |
3 ms |
340 KB |
Output is correct |
23 |
Correct |
5 ms |
468 KB |
Output is correct |
24 |
Correct |
17 ms |
816 KB |
Output is correct |
25 |
Correct |
19 ms |
720 KB |
Output is correct |
26 |
Correct |
335 ms |
75100 KB |
Output is correct |
27 |
Correct |
367 ms |
76904 KB |
Output is correct |
28 |
Correct |
19 ms |
852 KB |
Output is correct |
29 |
Correct |
4 ms |
980 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
3 ms |
468 KB |
Output is correct |
32 |
Correct |
2 ms |
468 KB |
Output is correct |
33 |
Correct |
29 ms |
4292 KB |
Output is correct |
34 |
Correct |
29 ms |
4288 KB |
Output is correct |
35 |
Execution timed out |
1088 ms |
23120 KB |
Time limit exceeded |
36 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
316 KB |
Output is correct |
9 |
Correct |
0 ms |
324 KB |
Output is correct |
10 |
Correct |
2 ms |
596 KB |
Output is correct |
11 |
Correct |
35 ms |
6668 KB |
Output is correct |
12 |
Correct |
389 ms |
80688 KB |
Output is correct |
13 |
Correct |
416 ms |
81096 KB |
Output is correct |
14 |
Correct |
28 ms |
4300 KB |
Output is correct |
15 |
Correct |
28 ms |
4252 KB |
Output is correct |
16 |
Correct |
4 ms |
852 KB |
Output is correct |
17 |
Correct |
20 ms |
2276 KB |
Output is correct |
18 |
Correct |
5 ms |
456 KB |
Output is correct |
19 |
Correct |
2 ms |
340 KB |
Output is correct |
20 |
Correct |
428 ms |
81072 KB |
Output is correct |
21 |
Correct |
7 ms |
468 KB |
Output is correct |
22 |
Correct |
3 ms |
340 KB |
Output is correct |
23 |
Correct |
5 ms |
452 KB |
Output is correct |
24 |
Correct |
17 ms |
772 KB |
Output is correct |
25 |
Correct |
19 ms |
716 KB |
Output is correct |
26 |
Correct |
335 ms |
75148 KB |
Output is correct |
27 |
Correct |
341 ms |
76872 KB |
Output is correct |
28 |
Correct |
19 ms |
824 KB |
Output is correct |
29 |
Correct |
4 ms |
980 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
3 ms |
468 KB |
Output is correct |
32 |
Correct |
2 ms |
468 KB |
Output is correct |
33 |
Correct |
29 ms |
4224 KB |
Output is correct |
34 |
Correct |
28 ms |
4300 KB |
Output is correct |
35 |
Execution timed out |
1077 ms |
23104 KB |
Time limit exceeded |
36 |
Halted |
0 ms |
0 KB |
- |