CSES - Datatähti 2024 loppu - Results
Submission details
Task:Retkeily
Sender:stpn129
Submission time:2024-01-20 16:17:13 +0200
Language:C++ (C++17)
Status:READY
Result:10
Feedback
groupverdictscore
#1ACCEPTED10
#20
#30
#40
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2, 3, 4details
#2ACCEPTED0.00 s1, 2, 3, 4details
#3ACCEPTED0.00 s1, 2, 3, 4details
#4ACCEPTED0.00 s1, 2, 3, 4details
#5ACCEPTED0.00 s1, 2, 3, 4details
#6ACCEPTED0.00 s1, 2, 4details
#7ACCEPTED0.00 s1, 2, 4details
#8ACCEPTED0.00 s1, 2, 3, 4details
#9ACCEPTED0.00 s1, 2, 4details
#10ACCEPTED0.01 s1, 2, 3, 4details
#11ACCEPTED0.00 s1, 2, 4details
#12ACCEPTED0.00 s1, 2, 4details
#13ACCEPTED0.00 s1, 2, 4details
#14ACCEPTED0.00 s1, 2, 4details
#15ACCEPTED0.01 s1, 2, 4details
#160.27 s2, 4details
#17--2, 4details
#18--2, 4details
#19--2, 3, 4details
#20--2, 4details
#21--2, 3, 4details
#22ACCEPTED0.00 s1, 3, 4details
#23ACCEPTED0.01 s1, 3, 4details
#24--3, 4details
#25--3, 4details
#26--3, 4details
#27--3, 4details
#28--3, 4details
#29ACCEPTED0.00 s1, 4details
#30ACCEPTED0.00 s1, 4details
#31ACCEPTED0.00 s1, 4details
#32ACCEPTED0.01 s1, 4details
#33ACCEPTED0.01 s1, 4details
#34ACCEPTED0.01 s1, 4details
#35ACCEPTED0.00 s1, 4details
#36ACCEPTED0.01 s1, 4details
#37--4details
#38--4details
#39--4details
#40--4details
#41--4details

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:

input
10000 1000
961 158
561 313
991 125
821 964
...

correct output
18

user output
10

Test 17

Group: 2, 4

Verdict:

input
1000 10000
428 1000
485 958
46 915
582 127
...

correct output
67

user output
(empty)

Test 18

Group: 2, 4

Verdict:

input
10000 10000
503 849
367 829
448 926
362 512
...

correct output
22

user output
(empty)

Test 19

Group: 2, 3, 4

Verdict:

input
100000 10000
111 705
808 24
69 858
961 122
...

correct output
7

user output
(empty)

Test 20

Group: 2, 4

Verdict:

input
10000 100000
844 874
339 315
819 918
627 936
...

correct output
27

user output
(empty)

Test 21

Group: 2, 3, 4

Verdict:

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:

input
10000 10000
636432 664736
341727 37864
469264 360610
545785 879043
...

correct output
10

user output
(empty)

Test 25

Group: 3, 4

Verdict:

input
100000 100000
750315 55215
550921 465416
435380 742666
288479 495099
...

correct output
7

user output
(empty)

Test 26

Group: 3, 4

Verdict:

input
100000 100000
416825 677767
347155 162523
602643 936386
181956 517732
...

correct output
8

user output
(empty)

Test 27

Group: 3, 4

Verdict:

input
100000 100000
155202 457283
421100 55104
604625 136495
841749 569346
...

correct output
9

user output
(empty)

Test 28

Group: 3, 4

Verdict:

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:

input
10000 10000
89066 605574
504488 66068
959128 348414
68004 849599
...

correct output
22936

user output
(empty)

Test 38

Group: 4

Verdict:

input
100000 100000
20824 214259
463783 904059
603615 769692
789080 399093
...

correct output
8070

user output
(empty)

Test 39

Group: 4

Verdict:

input
100000 100000
811424 464350
336948 946495
204883 914446
171888 431769
...

correct output
8240

user output
(empty)

Test 40

Group: 4

Verdict:

input
100000 100000
850810 902354
292608 63461
223139 188900
197760 995048
...

correct output
7769

user output
(empty)

Test 41

Group: 4

Verdict:

input
100000 100000
1 1
1 2
1 3
1 4
...

correct output
1899999

user output
(empty)