oj.uz

Submission #1053145

# Submission time Handle Problem Language Result Execution time Memory
1053145 2024-08-11T09:10:28 Z mychecksedad Fountain Parks (IOI21_parks) C++17
55 / 100
 400 ms 46804 KB 
#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long int
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define pii pair<int,int>
#define ff first
#define ss second
const int N = 3e5+100;

struct Dsu{
    vi p, s;
    void init(int n){
        p.resize(n);
        s.resize(n,1);
        for(int i = 0; i < n; ++i) p[i]=i;
    }
    int find(int v){
        if(p[v]==v) return v;
        return p[v]=find(p[v]);
    }
    void merge(int a, int b){
        a=find(a);b=find(b);
        if(a!=b){
            if(s[a]>s[b]) swap(a,b);
            p[a] = b;
            s[b] += s[a];
        }
    }
};

int arr[4][2] = {{2, 0}, {-2, 0}, {0, 2}, {0, -2}};

int construct_roads(std::vector<int> x, std::vector<int> y) {
  if (x.size() == 1) {
  build({}, {}, {}, {});
    return 1;
  }
  std::vector<int> U, V, a, b;
  // u.push_back(0);
  // v.push_back(1);
  // a.push_back(x[0]+1);
  // b.push_back(y[0]-1);
vector<array<int, 4>> g;
  int n = x.size();
  Dsu d; d.init(n);
  map<pair<int, int>, int> m;
  map<pair<int, int>, int> used;
  for(int i = 0; i < n; ++i){
    m[{x[i], y[i]}] = i + 1;
  }
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < 4; ++j){
      int nx = x[i] + arr[j][0];
      int ny = y[i] + arr[j][1];
      if(m.find({nx, ny}) != m.end()){
        int id = m[{nx, ny}];
        if(id > i) continue;
        int yy = y[i] + ny >> 1;
        int xx = x[i] + nx >> 1;
        int X = x[i], Y = y[i];
        // cout << X << ' ' << Y << ' ' << nx << ' ' << ny << '\n';
        if(nx < X) swap(X, nx), swap(Y, ny);
        if(ny < Y) swap(X, nx), swap(Y, ny);
        if(abs(nx - X) == 2){
          if((X/2+Y/2) % 2){
            g.pb({xx, Y - 1, i + 1, id});
          }else{
            g.pb({xx, Y + 1, i + 1, id});
          }
        }else{
          if((X/2 + Y/2) % 2 == 0){
            g.pb({X - 1, yy, i + 1, id});
          }else{
            g.pb({X + 1, yy, i + 1, id});
          }
        }   
      }
    }
  }
  sort(all(g));
  for(int i = 0; i < g.size(); ++i){
    int u = g[i][2], v = g[i][3];
    --u, --v;
    if(d.find(u) != d.find(v) && used[{g[i][0], g[i][1]}] == 0){
      d.merge(u, v);
      U.pb(u);
      V.pb(v);
      a.pb(g[i][0]);
      b.pb(g[i][1]);
      used[{g[i][0], g[i][1]}] = 1;
    }
  }
  if(d.s[d.find(0)] != n) return 0;


  build(U, V, a, b);
  return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:61:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |         int yy = y[i] + ny >> 1;
parks.cpp:62:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |         int xx = x[i] + nx >> 1;
parks.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for(int i = 0; i < g.size(); ++i){
      |                  ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 134 ms 21564 KB Output is correct
10 Correct 8 ms 2616 KB Output is correct
11 Correct 56 ms 11776 KB Output is correct
12 Correct 15 ms 3564 KB Output is correct
13 Correct 38 ms 8472 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 133 ms 21604 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 134 ms 21564 KB Output is correct
10 Correct 8 ms 2616 KB Output is correct
11 Correct 56 ms 11776 KB Output is correct
12 Correct 15 ms 3564 KB Output is correct
13 Correct 38 ms 8472 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 133 ms 21604 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 394 ms 44988 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 3 ms 900 KB Output is correct
27 Correct 4 ms 1116 KB Output is correct
28 Correct 130 ms 18044 KB Output is correct
29 Correct 207 ms 27860 KB Output is correct
30 Correct 293 ms 35780 KB Output is correct
31 Correct 387 ms 46804 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 344 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 392 KB Output is correct
43 Correct 2 ms 604 KB Output is correct
44 Correct 3 ms 860 KB Output is correct
45 Correct 149 ms 21604 KB Output is correct
46 Correct 232 ms 31892 KB Output is correct
47 Correct 234 ms 32448 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 134 ms 21564 KB Output is correct
10 Correct 8 ms 2616 KB Output is correct
11 Correct 56 ms 11776 KB Output is correct
12 Correct 15 ms 3564 KB Output is correct
13 Correct 38 ms 8472 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 133 ms 21604 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 394 ms 44988 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 3 ms 900 KB Output is correct
27 Correct 4 ms 1116 KB Output is correct
28 Correct 130 ms 18044 KB Output is correct
29 Correct 207 ms 27860 KB Output is correct
30 Correct 293 ms 35780 KB Output is correct
31 Correct 387 ms 46804 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 344 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 392 KB Output is correct
43 Correct 2 ms 604 KB Output is correct
44 Correct 3 ms 860 KB Output is correct
45 Correct 149 ms 21604 KB Output is correct
46 Correct 232 ms 31892 KB Output is correct
47 Correct 234 ms 32448 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Incorrect 400 ms 38880 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 134 ms 21564 KB Output is correct
10 Correct 8 ms 2616 KB Output is correct
11 Correct 56 ms 11776 KB Output is correct
12 Correct 15 ms 3564 KB Output is correct
13 Correct 38 ms 8472 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 133 ms 21604 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 326 ms 45352 KB Output is correct
21 Correct 364 ms 45212 KB Output is correct
22 Correct 338 ms 45760 KB Output is correct
23 Correct 257 ms 38840 KB Output is correct
24 Correct 177 ms 19308 KB Output is correct
25 Correct 356 ms 38060 KB Output is correct
26 Correct 300 ms 39292 KB Output is correct
27 Correct 356 ms 44480 KB Output is correct
28 Correct 343 ms 44348 KB Output is correct
29 Correct 390 ms 44972 KB Output is correct
30 Correct 397 ms 44228 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 20 ms 3688 KB Output is correct
33 Correct 76 ms 10296 KB Output is correct
34 Correct 333 ms 45760 KB Output is correct
35 Correct 10 ms 2260 KB Output is correct
36 Correct 69 ms 10040 KB Output is correct
37 Correct 151 ms 19628 KB Output is correct
38 Correct 125 ms 18484 KB Output is correct
39 Correct 183 ms 25084 KB Output is correct
40 Correct 254 ms 33208 KB Output is correct
41 Correct 317 ms 38904 KB Output is correct
42 Correct 394 ms 45420 KB Output is correct
43 Correct 0 ms 344 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Correct 0 ms 436 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 2 ms 604 KB Output is correct
55 Correct 3 ms 860 KB Output is correct
56 Correct 148 ms 22308 KB Output is correct
57 Correct 238 ms 33768 KB Output is correct
58 Correct 245 ms 34240 KB Output is correct
59 Correct 0 ms 348 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 0 ms 348 KB Output is correct
62 Correct 275 ms 44596 KB Output is correct
63 Correct 286 ms 44480 KB Output is correct
64 Correct 295 ms 44216 KB Output is correct
65 Correct 4 ms 1112 KB Output is correct
66 Correct 7 ms 1928 KB Output is correct
67 Correct 162 ms 22252 KB Output is correct
68 Correct 249 ms 34748 KB Output is correct
69 Correct 352 ms 44484 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 134 ms 21564 KB Output is correct
10 Correct 8 ms 2616 KB Output is correct
11 Correct 56 ms 11776 KB Output is correct
12 Correct 15 ms 3564 KB Output is correct
13 Correct 38 ms 8472 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 133 ms 21604 KB Output is correct
17 Correct 304 ms 43632 KB Output is correct
18 Correct 307 ms 45236 KB Output is correct
19 Correct 331 ms 45184 KB Output is correct
20 Correct 385 ms 44564 KB Output is correct
21 Correct 327 ms 39492 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 45 ms 7432 KB Output is correct
24 Correct 24 ms 4312 KB Output is correct
25 Correct 103 ms 14600 KB Output is correct
26 Correct 189 ms 24000 KB Output is correct
27 Correct 175 ms 23024 KB Output is correct
28 Correct 229 ms 30656 KB Output is correct
29 Correct 282 ms 35000 KB Output is correct
30 Correct 337 ms 40384 KB Output is correct
31 Correct 396 ms 46020 KB Output is correct
32 Correct 344 ms 45024 KB Output is correct
33 Correct 288 ms 44480 KB Output is correct
34 Correct 5 ms 1368 KB Output is correct
35 Correct 9 ms 2016 KB Output is correct
36 Correct 149 ms 22452 KB Output is correct
37 Correct 245 ms 34492 KB Output is correct
38 Correct 366 ms 44784 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 134 ms 21564 KB Output is correct
10 Correct 8 ms 2616 KB Output is correct
11 Correct 56 ms 11776 KB Output is correct
12 Correct 15 ms 3564 KB Output is correct
13 Correct 38 ms 8472 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 133 ms 21604 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 394 ms 44988 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 3 ms 900 KB Output is correct
27 Correct 4 ms 1116 KB Output is correct
28 Correct 130 ms 18044 KB Output is correct
29 Correct 207 ms 27860 KB Output is correct
30 Correct 293 ms 35780 KB Output is correct
31 Correct 387 ms 46804 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 344 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 392 KB Output is correct
43 Correct 2 ms 604 KB Output is correct
44 Correct 3 ms 860 KB Output is correct
45 Correct 149 ms 21604 KB Output is correct
46 Correct 232 ms 31892 KB Output is correct
47 Correct 234 ms 32448 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Incorrect 400 ms 38880 KB Solution announced impossible, but it is possible.
56 Halted 0 ms 0 KB -