oj.uz

Submission #446593

# Submission time Handle Problem Language Result Execution time Memory
446593 2021-07-22T14:13:40 Z SuffixAutomata Fountain Parks (IOI21_parks) C++17
55 / 100
 1254 ms 73648 KB 
#include "parks.h"
 
#include <bits/stdc++.h>
using namespace std;
 
int ufs[200005];
int ge(int x) {
  if (ufs[x] == -1)
    return x;
  return ufs[x] = ge(ufs[x]);
}
 
vector<pair<int, int>> pts;
map<pair<int, int>, int> idx;
vector<pair<int, int>> elist;
int n;
 
mt19937 rng(108616);
 
vector<int> bpt[200005];
int mach[800005];
int vis[200005];
int gloti = 0;
bool dfs(int u, int ti) {
  vis[u] = ti;
  for (int v : bpt[u]) {
    if (mach[v] == -1 || ((vis[mach[v]] != ti) && dfs(mach[v], ti))) {
      mach[v] = u;
      return 1;
    }
  }
  return 0;
}
bool hasmxm(int cnt) {
  for (int i = 0; i < cnt; i++) {
    gloti++;
    if (!dfs(i, gloti))
      return 0;
  }
  return 1;
}
bool ranAttempt() {
  shuffle(elist.begin(), elist.end(), rng);
  memset(ufs, -1, sizeof ufs);
  vector<pair<int, int>> mst;
  for (auto [u, v] : elist) {
    if (ge(u) != ge(v)) {
      ufs[ge(u)] = ge(v);
      mst.push_back({u, v});
    }
  }
  if (mst.size() != n - 1)
    return 0;
  map<pair<int, int>, int> benches;
 
  int edid = 0, beid = 0;
  for (auto [u, v] : mst) {
    auto [x1, y1] = pts[u];
    auto [x2, y2] = pts[v];
    bpt[edid].clear();
    if (x1 == x2) {
      int c = min(y1, y2);
      pair<int, int> p1 = {x1 - 1, c + 1}, p2 = {x1 + 1, c + 1};
      if (!benches.count(p1))
        benches[p1] = beid++;
      if (!benches.count(p2))
        benches[p2] = beid++;
      bpt[edid].push_back(benches[p1]);
      bpt[edid].push_back(benches[p2]);
    } else {
      int c = min(x1, x2);
      pair<int, int> p1 = {c + 1, y1 + 1}, p2 = {c + 1, y1 - 1};
      if (!benches.count(p1))
        benches[p1] = beid++;
      if (!benches.count(p2))
        benches[p2] = beid++;
      bpt[edid].push_back(benches[p1]);
      bpt[edid].push_back(benches[p2]);
    }
    edid++;
  }
  for (int i = 0; i < beid; i++)
    mach[i] = -1;
  if (hasmxm(edid)) {
    vector<int> U, V;
    vector<int> mx(mst.size()), my(mst.size());
    for (auto [u, v] : mst) {
      U.push_back(u);
      V.push_back(v);
    }
    for (auto [x, i] : benches) {
      if (mach[i] == -1)
        continue;
      auto [zx, zy] = x;
      mx[mach[i]] = zx;
      my[mach[i]] = zy;
    }
    build(U, V, mx, my);
    return 1;
  }
  return 0;
}
 
int construct_roads(std::vector<int> x, std::vector<int> y) {
  if (x.size() == 1) {
    build({}, {}, {}, {});
    return 1;
  }
  n = x.size();
  pts = vector<pair<int, int>>(n);
  for (int i = 0; i < n; i++) {
    pts[i] = {x[i], y[i]};
    idx[pts[i]] = i;
  }
  for (int i = 0; i < n; i++) {
    if (idx.count({x[i] + 2, y[i]}))
      elist.push_back({i, idx[{x[i] + 2, y[i]}]});
    if (idx.count({x[i], y[i] + 2}))
      elist.push_back({i, idx[{x[i], y[i] + 2}]});
  }
  while (clock() < CLOCKS_PER_SEC) {
    if (ranAttempt())
      return 1;
  }
  return 0;
}

Compilation message

parks.cpp: In function 'bool ranAttempt()':
parks.cpp:52:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |   if (mst.size() != n - 1)
      |       ~~~~~~~~~~~^~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 1000 ms 5780 KB Output is correct
4 Correct 3 ms 5708 KB Output is correct
5 Correct 4 ms 5776 KB Output is correct
6 Correct 1000 ms 5768 KB Output is correct
7 Correct 1000 ms 5768 KB Output is correct
8 Correct 1000 ms 5764 KB Output is correct
9 Correct 381 ms 39192 KB Output is correct
10 Correct 26 ms 9080 KB Output is correct
11 Correct 169 ms 23636 KB Output is correct
12 Correct 41 ms 10740 KB Output is correct
13 Correct 1002 ms 11476 KB Output is correct
14 Correct 1000 ms 5956 KB Output is correct
15 Correct 1000 ms 6128 KB Output is correct
16 Correct 373 ms 39348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 1000 ms 5780 KB Output is correct
4 Correct 3 ms 5708 KB Output is correct
5 Correct 4 ms 5776 KB Output is correct
6 Correct 1000 ms 5768 KB Output is correct
7 Correct 1000 ms 5768 KB Output is correct
8 Correct 1000 ms 5764 KB Output is correct
9 Correct 381 ms 39192 KB Output is correct
10 Correct 26 ms 9080 KB Output is correct
11 Correct 169 ms 23636 KB Output is correct
12 Correct 41 ms 10740 KB Output is correct
13 Correct 1002 ms 11476 KB Output is correct
14 Correct 1000 ms 5956 KB Output is correct
15 Correct 1000 ms 6128 KB Output is correct
16 Correct 373 ms 39348 KB Output is correct
17 Correct 4 ms 5708 KB Output is correct
18 Correct 3 ms 5708 KB Output is correct
19 Correct 3 ms 5708 KB Output is correct
20 Correct 3 ms 5708 KB Output is correct
21 Correct 1000 ms 5764 KB Output is correct
22 Correct 4 ms 5708 KB Output is correct
23 Correct 916 ms 64124 KB Output is correct
24 Correct 4 ms 5708 KB Output is correct
25 Correct 6 ms 6092 KB Output is correct
26 Correct 1000 ms 6092 KB Output is correct
27 Correct 1000 ms 6256 KB Output is correct
28 Correct 326 ms 28296 KB Output is correct
29 Correct 493 ms 40768 KB Output is correct
30 Correct 705 ms 50928 KB Output is correct
31 Correct 902 ms 64284 KB Output is correct
32 Correct 4 ms 5708 KB Output is correct
33 Correct 4 ms 5708 KB Output is correct
34 Correct 3 ms 5708 KB Output is correct
35 Correct 1000 ms 5784 KB Output is correct
36 Correct 1000 ms 5828 KB Output is correct
37 Correct 4 ms 5708 KB Output is correct
38 Correct 4 ms 5708 KB Output is correct
39 Correct 4 ms 5776 KB Output is correct
40 Correct 3 ms 5784 KB Output is correct
41 Correct 1000 ms 5764 KB Output is correct
42 Correct 4 ms 5708 KB Output is correct
43 Correct 1000 ms 5992 KB Output is correct
44 Correct 1000 ms 6212 KB Output is correct
45 Correct 383 ms 35156 KB Output is correct
46 Correct 597 ms 47916 KB Output is correct
47 Correct 595 ms 47952 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 1000 ms 5780 KB Output is correct
4 Correct 3 ms 5708 KB Output is correct
5 Correct 4 ms 5776 KB Output is correct
6 Correct 1000 ms 5768 KB Output is correct
7 Correct 1000 ms 5768 KB Output is correct
8 Correct 1000 ms 5764 KB Output is correct
9 Correct 381 ms 39192 KB Output is correct
10 Correct 26 ms 9080 KB Output is correct
11 Correct 169 ms 23636 KB Output is correct
12 Correct 41 ms 10740 KB Output is correct
13 Correct 1002 ms 11476 KB Output is correct
14 Correct 1000 ms 5956 KB Output is correct
15 Correct 1000 ms 6128 KB Output is correct
16 Correct 373 ms 39348 KB Output is correct
17 Correct 4 ms 5708 KB Output is correct
18 Correct 3 ms 5708 KB Output is correct
19 Correct 3 ms 5708 KB Output is correct
20 Correct 3 ms 5708 KB Output is correct
21 Correct 1000 ms 5764 KB Output is correct
22 Correct 4 ms 5708 KB Output is correct
23 Correct 916 ms 64124 KB Output is correct
24 Correct 4 ms 5708 KB Output is correct
25 Correct 6 ms 6092 KB Output is correct
26 Correct 1000 ms 6092 KB Output is correct
27 Correct 1000 ms 6256 KB Output is correct
28 Correct 326 ms 28296 KB Output is correct
29 Correct 493 ms 40768 KB Output is correct
30 Correct 705 ms 50928 KB Output is correct
31 Correct 902 ms 64284 KB Output is correct
32 Correct 4 ms 5708 KB Output is correct
33 Correct 4 ms 5708 KB Output is correct
34 Correct 3 ms 5708 KB Output is correct
35 Correct 1000 ms 5784 KB Output is correct
36 Correct 1000 ms 5828 KB Output is correct
37 Correct 4 ms 5708 KB Output is correct
38 Correct 4 ms 5708 KB Output is correct
39 Correct 4 ms 5776 KB Output is correct
40 Correct 3 ms 5784 KB Output is correct
41 Correct 1000 ms 5764 KB Output is correct
42 Correct 4 ms 5708 KB Output is correct
43 Correct 1000 ms 5992 KB Output is correct
44 Correct 1000 ms 6212 KB Output is correct
45 Correct 383 ms 35156 KB Output is correct
46 Correct 597 ms 47916 KB Output is correct
47 Correct 595 ms 47952 KB Output is correct
48 Correct 4 ms 5708 KB Output is correct
49 Correct 4 ms 5708 KB Output is correct
50 Correct 3 ms 5708 KB Output is correct
51 Correct 3 ms 5708 KB Output is correct
52 Correct 3 ms 5708 KB Output is correct
53 Correct 4 ms 5780 KB Output is correct
54 Correct 4 ms 5708 KB Output is correct
55 Incorrect 1254 ms 53048 KB Solution announced impossible, but it is possible.
56 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 1000 ms 5780 KB Output is correct
4 Correct 3 ms 5708 KB Output is correct
5 Correct 4 ms 5776 KB Output is correct
6 Correct 1000 ms 5768 KB Output is correct
7 Correct 1000 ms 5768 KB Output is correct
8 Correct 1000 ms 5764 KB Output is correct
9 Correct 381 ms 39192 KB Output is correct
10 Correct 26 ms 9080 KB Output is correct
11 Correct 169 ms 23636 KB Output is correct
12 Correct 41 ms 10740 KB Output is correct
13 Correct 1002 ms 11476 KB Output is correct
14 Correct 1000 ms 5956 KB Output is correct
15 Correct 1000 ms 6128 KB Output is correct
16 Correct 373 ms 39348 KB Output is correct
17 Correct 3 ms 5776 KB Output is correct
18 Correct 4 ms 5780 KB Output is correct
19 Correct 1000 ms 5776 KB Output is correct
20 Correct 816 ms 61036 KB Output is correct
21 Correct 1091 ms 65028 KB Output is correct
22 Correct 844 ms 60512 KB Output is correct
23 Correct 753 ms 62768 KB Output is correct
24 Correct 1022 ms 24716 KB Output is correct
25 Correct 1029 ms 29988 KB Output is correct
26 Correct 1022 ms 29864 KB Output is correct
27 Correct 937 ms 72364 KB Output is correct
28 Correct 942 ms 72412 KB Output is correct
29 Correct 1067 ms 72444 KB Output is correct
30 Correct 958 ms 72540 KB Output is correct
31 Correct 4 ms 5708 KB Output is correct
32 Correct 43 ms 9960 KB Output is correct
33 Correct 1008 ms 15652 KB Output is correct
34 Correct 1002 ms 64380 KB Output is correct
35 Correct 1000 ms 7092 KB Output is correct
36 Correct 1004 ms 11996 KB Output is correct
37 Correct 1010 ms 18384 KB Output is correct
38 Correct 302 ms 28976 KB Output is correct
39 Correct 429 ms 37520 KB Output is correct
40 Correct 588 ms 45980 KB Output is correct
41 Correct 774 ms 54340 KB Output is correct
42 Correct 999 ms 63740 KB Output is correct
43 Correct 4 ms 5708 KB Output is correct
44 Correct 4 ms 5708 KB Output is correct
45 Correct 3 ms 5784 KB Output is correct
46 Correct 1000 ms 5780 KB Output is correct
47 Correct 1000 ms 5776 KB Output is correct
48 Correct 4 ms 5708 KB Output is correct
49 Correct 3 ms 5772 KB Output is correct
50 Correct 4 ms 5708 KB Output is correct
51 Correct 4 ms 5708 KB Output is correct
52 Correct 1000 ms 5780 KB Output is correct
53 Correct 3 ms 5708 KB Output is correct
54 Correct 1000 ms 5996 KB Output is correct
55 Correct 1000 ms 6132 KB Output is correct
56 Correct 387 ms 35088 KB Output is correct
57 Correct 586 ms 47960 KB Output is correct
58 Correct 646 ms 48084 KB Output is correct
59 Correct 1000 ms 5708 KB Output is correct
60 Correct 3 ms 5708 KB Output is correct
61 Correct 1000 ms 5776 KB Output is correct
62 Correct 898 ms 72520 KB Output is correct
63 Correct 928 ms 72632 KB Output is correct
64 Correct 920 ms 72316 KB Output is correct
65 Correct 1000 ms 6252 KB Output is correct
66 Correct 1000 ms 6604 KB Output is correct
67 Correct 385 ms 34752 KB Output is correct
68 Correct 638 ms 49036 KB Output is correct
69 Correct 981 ms 63660 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 1000 ms 5780 KB Output is correct
4 Correct 3 ms 5708 KB Output is correct
5 Correct 4 ms 5776 KB Output is correct
6 Correct 1000 ms 5768 KB Output is correct
7 Correct 1000 ms 5768 KB Output is correct
8 Correct 1000 ms 5764 KB Output is correct
9 Correct 381 ms 39192 KB Output is correct
10 Correct 26 ms 9080 KB Output is correct
11 Correct 169 ms 23636 KB Output is correct
12 Correct 41 ms 10740 KB Output is correct
13 Correct 1002 ms 11476 KB Output is correct
14 Correct 1000 ms 5956 KB Output is correct
15 Correct 1000 ms 6128 KB Output is correct
16 Correct 373 ms 39348 KB Output is correct
17 Correct 925 ms 73304 KB Output is correct
18 Correct 927 ms 73648 KB Output is correct
19 Correct 968 ms 68832 KB Output is correct
20 Correct 1012 ms 62076 KB Output is correct
21 Correct 834 ms 60348 KB Output is correct
22 Correct 4 ms 5708 KB Output is correct
23 Correct 94 ms 15336 KB Output is correct
24 Correct 1002 ms 8520 KB Output is correct
25 Correct 1006 ms 14968 KB Output is correct
26 Correct 1012 ms 20912 KB Output is correct
27 Correct 387 ms 35352 KB Output is correct
28 Correct 560 ms 43792 KB Output is correct
29 Correct 662 ms 49924 KB Output is correct
30 Correct 814 ms 57240 KB Output is correct
31 Correct 998 ms 64700 KB Output is correct
32 Correct 946 ms 65632 KB Output is correct
33 Correct 933 ms 72500 KB Output is correct
34 Correct 1000 ms 6468 KB Output is correct
35 Correct 1002 ms 7024 KB Output is correct
36 Correct 377 ms 34860 KB Output is correct
37 Correct 642 ms 49516 KB Output is correct
38 Correct 968 ms 64524 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 1000 ms 5780 KB Output is correct
4 Correct 3 ms 5708 KB Output is correct
5 Correct 4 ms 5776 KB Output is correct
6 Correct 1000 ms 5768 KB Output is correct
7 Correct 1000 ms 5768 KB Output is correct
8 Correct 1000 ms 5764 KB Output is correct
9 Correct 381 ms 39192 KB Output is correct
10 Correct 26 ms 9080 KB Output is correct
11 Correct 169 ms 23636 KB Output is correct
12 Correct 41 ms 10740 KB Output is correct
13 Correct 1002 ms 11476 KB Output is correct
14 Correct 1000 ms 5956 KB Output is correct
15 Correct 1000 ms 6128 KB Output is correct
16 Correct 373 ms 39348 KB Output is correct
17 Correct 4 ms 5708 KB Output is correct
18 Correct 3 ms 5708 KB Output is correct
19 Correct 3 ms 5708 KB Output is correct
20 Correct 3 ms 5708 KB Output is correct
21 Correct 1000 ms 5764 KB Output is correct
22 Correct 4 ms 5708 KB Output is correct
23 Correct 916 ms 64124 KB Output is correct
24 Correct 4 ms 5708 KB Output is correct
25 Correct 6 ms 6092 KB Output is correct
26 Correct 1000 ms 6092 KB Output is correct
27 Correct 1000 ms 6256 KB Output is correct
28 Correct 326 ms 28296 KB Output is correct
29 Correct 493 ms 40768 KB Output is correct
30 Correct 705 ms 50928 KB Output is correct
31 Correct 902 ms 64284 KB Output is correct
32 Correct 4 ms 5708 KB Output is correct
33 Correct 4 ms 5708 KB Output is correct
34 Correct 3 ms 5708 KB Output is correct
35 Correct 1000 ms 5784 KB Output is correct
36 Correct 1000 ms 5828 KB Output is correct
37 Correct 4 ms 5708 KB Output is correct
38 Correct 4 ms 5708 KB Output is correct
39 Correct 4 ms 5776 KB Output is correct
40 Correct 3 ms 5784 KB Output is correct
41 Correct 1000 ms 5764 KB Output is correct
42 Correct 4 ms 5708 KB Output is correct
43 Correct 1000 ms 5992 KB Output is correct
44 Correct 1000 ms 6212 KB Output is correct
45 Correct 383 ms 35156 KB Output is correct
46 Correct 597 ms 47916 KB Output is correct
47 Correct 595 ms 47952 KB Output is correct
48 Correct 4 ms 5708 KB Output is correct
49 Correct 4 ms 5708 KB Output is correct
50 Correct 3 ms 5708 KB Output is correct
51 Correct 3 ms 5708 KB Output is correct
52 Correct 3 ms 5708 KB Output is correct
53 Correct 4 ms 5780 KB Output is correct
54 Correct 4 ms 5708 KB Output is correct
55 Incorrect 1254 ms 53048 KB Solution announced impossible, but it is possible.
56 Halted 0 ms 0 KB -