Task: | Retkeily |
Sender: | stpn129 |
Submission time: | 2024-01-20 16:17:13 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 10 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 10 |
#2 | WRONG ANSWER | 0 |
#3 | TIME LIMIT EXCEEDED | 0 |
#4 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.00 s | 1, 2, 3, 4 | details |
#2 | ACCEPTED | 0.00 s | 1, 2, 3, 4 | details |
#3 | ACCEPTED | 0.00 s | 1, 2, 3, 4 | details |
#4 | ACCEPTED | 0.00 s | 1, 2, 3, 4 | details |
#5 | ACCEPTED | 0.00 s | 1, 2, 3, 4 | details |
#6 | ACCEPTED | 0.00 s | 1, 2, 4 | details |
#7 | ACCEPTED | 0.00 s | 1, 2, 4 | details |
#8 | ACCEPTED | 0.00 s | 1, 2, 3, 4 | details |
#9 | ACCEPTED | 0.00 s | 1, 2, 4 | details |
#10 | ACCEPTED | 0.01 s | 1, 2, 3, 4 | details |
#11 | ACCEPTED | 0.00 s | 1, 2, 4 | details |
#12 | ACCEPTED | 0.00 s | 1, 2, 4 | details |
#13 | ACCEPTED | 0.00 s | 1, 2, 4 | details |
#14 | ACCEPTED | 0.00 s | 1, 2, 4 | details |
#15 | ACCEPTED | 0.01 s | 1, 2, 4 | details |
#16 | WRONG ANSWER | 0.27 s | 2, 4 | details |
#17 | TIME LIMIT EXCEEDED | -- | 2, 4 | details |
#18 | TIME LIMIT EXCEEDED | -- | 2, 4 | details |
#19 | TIME LIMIT EXCEEDED | -- | 2, 3, 4 | details |
#20 | TIME LIMIT EXCEEDED | -- | 2, 4 | details |
#21 | TIME LIMIT EXCEEDED | -- | 2, 3, 4 | details |
#22 | ACCEPTED | 0.00 s | 1, 3, 4 | details |
#23 | ACCEPTED | 0.01 s | 1, 3, 4 | details |
#24 | TIME LIMIT EXCEEDED | -- | 3, 4 | details |
#25 | TIME LIMIT EXCEEDED | -- | 3, 4 | details |
#26 | TIME LIMIT EXCEEDED | -- | 3, 4 | details |
#27 | TIME LIMIT EXCEEDED | -- | 3, 4 | details |
#28 | TIME LIMIT EXCEEDED | -- | 3, 4 | details |
#29 | ACCEPTED | 0.00 s | 1, 4 | details |
#30 | ACCEPTED | 0.00 s | 1, 4 | details |
#31 | ACCEPTED | 0.00 s | 1, 4 | details |
#32 | ACCEPTED | 0.01 s | 1, 4 | details |
#33 | ACCEPTED | 0.01 s | 1, 4 | details |
#34 | ACCEPTED | 0.01 s | 1, 4 | details |
#35 | ACCEPTED | 0.00 s | 1, 4 | details |
#36 | ACCEPTED | 0.01 s | 1, 4 | details |
#37 | TIME LIMIT EXCEEDED | -- | 4 | details |
#38 | TIME LIMIT EXCEEDED | -- | 4 | details |
#39 | TIME LIMIT EXCEEDED | -- | 4 | details |
#40 | TIME LIMIT EXCEEDED | -- | 4 | details |
#41 | TIME LIMIT EXCEEDED | -- | 4 | details |
Code
#include<bits/stdc++.h> #define int long long using namespace std; void init_code(){ ios_base::sync_with_stdio(false); cin.tie(NULL); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif } bool ok (int n, int m, pair<int, int> t) { return (t.first >= 1 && t.first <= n) && (t.second >= 1 && t.first <= m); } const int inf = 1e10 + 7; void solve() { int n, m; cin >> n >> m; vector<pair<int, int>> res(n), free(m); map<pair<int, int>, int> res2; for (int i = 0; i < n; ++i) { cin >> res[i].first >> res[i].second; res2[res[i]] = 1; } for (int i = 0; i < m; ++i) { cin >> free[i].first >> free[i].second; } if (n <= 1000 && m <= 1000) { int ans = -inf; for (int i = 0; i < m; ++i) { int cur = inf; for (int j = 0; j < n; ++j) { cur = min(cur, abs(res[j].first - free[i].first) + abs(res[j].second - free[i].second)); } ans = max(ans, cur); } cout << ans << '\n'; return; } vector<pair<int, int>> mv = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; int ans = 0; for (int i = 0; i < m; ++i) { map<pair<int, int>, int> dist; queue<pair<int, int>> q; dist[free[i]] = 0; q.push(free[i]); while (!q.empty()) { pair<int, int> v = q.front(); q.pop(); if (res2[v]) { ans = max(ans, dist[v]); continue; } if (dist[v] >= 10) { continue; } for (auto k : mv) { pair<int, int> nw = {v.first + k.first, v.second + k.second}; if (!dist.count(nw) || dist[nw] > dist[v] + 1) { dist[nw] = dist[v] + 1; q.push(nw); } } } } cout << ans << '\n'; } signed main() { init_code(); solve(); return 0; }
Test details
Test 1
Group: 1, 2, 3, 4
Verdict: ACCEPTED
input |
---|
1 1 6 6 8 9 |
correct output |
---|
5 |
user output |
---|
5 |
Test 2
Group: 1, 2, 3, 4
Verdict: ACCEPTED
input |
---|
5 5 5 10 8 10 1 2 4 10 ... |
correct output |
---|
4 |
user output |
---|
4 |
Test 3
Group: 1, 2, 3, 4
Verdict: ACCEPTED
input |
---|
10 10 5 2 1 10 6 10 5 5 ... |
correct output |
---|
5 |
user output |
---|
5 |
Test 4
Group: 1, 2, 3, 4
Verdict: ACCEPTED
input |
---|
10 5 6 1 8 9 3 2 6 6 ... |
correct output |
---|
3 |
user output |
---|
3 |
Test 5
Group: 1, 2, 3, 4
Verdict: ACCEPTED
input |
---|
5 10 10 10 6 2 10 9 8 7 ... |
correct output |
---|
7 |
user output |
---|
7 |
Test 6
Group: 1, 2, 4
Verdict: ACCEPTED
input |
---|
1 1 55 68 28 42 |
correct output |
---|
53 |
user output |
---|
53 |
Test 7
Group: 1, 2, 4
Verdict: ACCEPTED
input |
---|
100 100 52 56 58 96 3 99 18 1 ... |
correct output |
---|
20 |
user output |
---|
20 |
Test 8
Group: 1, 2, 3, 4
Verdict: ACCEPTED
input |
---|
1000 100 60 40 68 47 30 32 74 52 ... |
correct output |
---|
5 |
user output |
---|
5 |
Test 9
Group: 1, 2, 4
Verdict: ACCEPTED
input |
---|
100 1000 44 26 18 81 18 6 83 90 ... |
correct output |
---|
20 |
user output |
---|
20 |
Test 10
Group: 1, 2, 3, 4
Verdict: ACCEPTED
input |
---|
1000 1000 15 13 23 79 81 43 30 40 ... |
correct output |
---|
7 |
user output |
---|
7 |
Test 11
Group: 1, 2, 4
Verdict: ACCEPTED
input |
---|
1 1 948 495 227 149 |
correct output |
---|
1067 |
user output |
---|
1067 |
Test 12
Group: 1, 2, 4
Verdict: ACCEPTED
input |
---|
100 100 114 530 748 841 612 709 810 232 ... |
correct output |
---|
203 |
user output |
---|
203 |
Test 13
Group: 1, 2, 4
Verdict: ACCEPTED
input |
---|
1000 100 225 82 265 691 978 367 993 396 ... |
correct output |
---|
50 |
user output |
---|
50 |
Test 14
Group: 1, 2, 4
Verdict: ACCEPTED
input |
---|
100 1000 848 668 189 716 451 80 626 973 ... |
correct output |
---|
192 |
user output |
---|
192 |
Test 15
Group: 1, 2, 4
Verdict: ACCEPTED
input |
---|
1000 1000 931 656 382 809 666 609 1000 923 ... |
correct output |
---|
66 |
user output |
---|
66 |
Test 16
Group: 2, 4
Verdict: WRONG ANSWER
input |
---|
10000 1000 961 158 561 313 991 125 821 964 ... |
correct output |
---|
18 |
user output |
---|
10 |
Test 17
Group: 2, 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 10000 428 1000 485 958 46 915 582 127 ... |
correct output |
---|
67 |
user output |
---|
(empty) |
Test 18
Group: 2, 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
10000 10000 503 849 367 829 448 926 362 512 ... |
correct output |
---|
22 |
user output |
---|
(empty) |
Test 19
Group: 2, 3, 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 10000 111 705 808 24 69 858 961 122 ... |
correct output |
---|
7 |
user output |
---|
(empty) |
Test 20
Group: 2, 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
10000 100000 844 874 339 315 819 918 627 936 ... |
correct output |
---|
27 |
user output |
---|
(empty) |
Test 21
Group: 2, 3, 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 100000 100 468 303 899 784 458 505 54 ... |
correct output |
---|
8 |
user output |
---|
(empty) |
Test 22
Group: 1, 3, 4
Verdict: ACCEPTED
input |
---|
10 10 451219 220496 369161 161920 241139 700531 811276 993633 ... |
correct output |
---|
10 |
user output |
---|
10 |
Test 23
Group: 1, 3, 4
Verdict: ACCEPTED
input |
---|
1000 1000 337358 113599 674585 852084 717817 983395 895431 391144 ... |
correct output |
---|
10 |
user output |
---|
10 |
Test 24
Group: 3, 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
10000 10000 636432 664736 341727 37864 469264 360610 545785 879043 ... |
correct output |
---|
10 |
user output |
---|
(empty) |
Test 25
Group: 3, 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 100000 750315 55215 550921 465416 435380 742666 288479 495099 ... |
correct output |
---|
7 |
user output |
---|
(empty) |
Test 26
Group: 3, 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 100000 416825 677767 347155 162523 602643 936386 181956 517732 ... |
correct output |
---|
8 |
user output |
---|
(empty) |
Test 27
Group: 3, 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 100000 155202 457283 421100 55104 604625 136495 841749 569346 ... |
correct output |
---|
9 |
user output |
---|
(empty) |
Test 28
Group: 3, 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 100000 290146 808578 489810 268578 956361 635214 939844 534435 ... |
correct output |
---|
10 |
user output |
---|
(empty) |
Test 29
Group: 1, 4
Verdict: ACCEPTED
input |
---|
10 10 668880 791821 226050 188133 859493 736633 290460 838926 ... |
correct output |
---|
342068 |
user output |
---|
342068 |
Test 30
Group: 1, 4
Verdict: ACCEPTED
input |
---|
100 100 729367 697755 338457 742774 535371 701216 93743 555995 ... |
correct output |
---|
285526 |
user output |
---|
285526 |
Test 31
Group: 1, 4
Verdict: ACCEPTED
input |
---|
100 1000 50870 539657 476809 462765 311713 355546 901838 829393 ... |
correct output |
---|
255789 |
user output |
---|
255789 |
Test 32
Group: 1, 4
Verdict: ACCEPTED
input |
---|
1000 100 182415 659794 581623 510256 594984 525993 367726 938015 ... |
correct output |
---|
50501 |
user output |
---|
50501 |
Test 33
Group: 1, 4
Verdict: ACCEPTED
input |
---|
1000 1000 668976 422918 350791 933024 893307 88057 278098 13847 ... |
correct output |
---|
57897 |
user output |
---|
57897 |
Test 34
Group: 1, 4
Verdict: ACCEPTED
input |
---|
1000 1000 701742 116334 278337 368995 187245 133297 273083 369187 ... |
correct output |
---|
60537 |
user output |
---|
60537 |
Test 35
Group: 1, 4
Verdict: ACCEPTED
input |
---|
10 10 693836 74759 61731 520849 666762 45364 559335 979511 ... |
correct output |
---|
417182 |
user output |
---|
417182 |
Test 36
Group: 1, 4
Verdict: ACCEPTED
input |
---|
1000 1000 207572 43521 513003 683552 58800 253576 16541 558695 ... |
correct output |
---|
69609 |
user output |
---|
69609 |
Test 37
Group: 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
10000 10000 89066 605574 504488 66068 959128 348414 68004 849599 ... |
correct output |
---|
22936 |
user output |
---|
(empty) |
Test 38
Group: 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 100000 20824 214259 463783 904059 603615 769692 789080 399093 ... |
correct output |
---|
8070 |
user output |
---|
(empty) |
Test 39
Group: 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 100000 811424 464350 336948 946495 204883 914446 171888 431769 ... |
correct output |
---|
8240 |
user output |
---|
(empty) |
Test 40
Group: 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 100000 850810 902354 292608 63461 223139 188900 197760 995048 ... |
correct output |
---|
7769 |
user output |
---|
(empty) |
Test 41
Group: 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
100000 100000 1 1 1 2 1 3 1 4 ... |
correct output |
---|
1899999 |
user output |
---|
(empty) |