oj.uz

Submission #832859

# Submission time Handle Problem Language Result Execution time Memory
832859 2023-08-21T16:03:14 Z Ronin13 Fountain Parks (IOI21_parks) C++17
55 / 100
 1977 ms 143660 KB 
#include "parks.h"
#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned ll
#define f first
#define s second 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb empalce_back
using namespace std;

map <pair<pii, pii> , int> mp;
map <pii, bool> mark; 
map <pii, int> ind;
const int nmax = 200001;
vector <int> p(nmax);
vector <int> sz(nmax);
vector <int> u, v;
vector <int> a, b;
vector <int> x, y;
vector <bool> used(nmax);
void make_set(int v){
    p[v] = v;
    sz[v] = 1;
}
int find_set(int v){
    return p[v] == v ? v : p[v] = find_set(p[v]);
}

void union_sets(int a, int b){
    if(find_set(a) == find_set(b)) return;
    mp[{{x[a - 1], y[a - 1]}, {x[b - 1], y[b -1]}}] = u.size() + 1;
    mp[{{x[b - 1], y[b - 1]}, {x[a - 1], y[a - 1]}}] = u.size() + 1;
    u.pb(a - 1);
    v.pb(b - 1);
    a = find_set(a);
    b = find_set(b);
    if(sz[a] < sz[b]) swap(a, b);
    p[b] = a;
    sz[a] += sz[b];
}

pii mark_vertical_line(int ind){
    ind--;
    //cout << ind << ' ';
    pair <pii, pii> seg = {{x[u[ind]],y[u[ind]]}, {x[v[ind]], y[v[ind]]}};
    pii A = {seg.f.f - 1, seg.f.s / 2 + seg.s.s / 2};
    if(!mark[A]){
        mark[A] = true;
        return A;
    }
    A.f += 2;
    mark[A] = true;
    return A;
}

pii mark_horizontal_line(int ind){
    ind--;
    pair <pii, pii> seg = {{x[u[ind]],y[u[ind]]}, {x[v[ind]], y[v[ind]]}};
    pii A = {seg.f.f / 2 + seg.s.f / 2, seg.f.s - 1};
    if(!mark[A]){
        mark[A] = true;
        return A;
    }
    A.s += 2;
    mark[A] = true;
    return A;
}

int construct_roads(std::vector<int> X, std::vector<int> Y) {
    x = X, y = Y;
    int n = x.size();
    for(int i = 0; i < n; i++){
        ind[{x[i], y[i]}] = i + 1;
    }
    for(int i= 1; i <= n; i++)
        make_set(i);
    
    for(int i = 0; i < n; i++){
        if(ind[{x[i], y[i] - 2}])
            union_sets(ind[{x[i], y[i] - 2}], i + 1);
        if(ind[{x[i], y[i] + 2}])
            union_sets(ind[{x[i], y[i] + 2}], i + 1);
    }
    for(int i = 0; i < n; i++){
        if(ind[{x[i] + 2, y[i]}])
            union_sets(ind[{x[i] + 2, y[i]}], i + 1);
        if(ind[{x[i] - 2, y[i]}])
            union_sets(ind[{x[i] - 2, y[i]}], i + 1);
    }
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        if(find_set(i) == i) cnt++;
    }
    if(cnt > 1) return 0;
    a.resize(u.size());
    b.resize(v.size());
   
    set <int> st;
    for(int i = 1; i <= u.size(); i++)
        st.insert(i);
    while(!st.empty()){
        int s = *st.begin();
        st.erase(st.begin());
      // cout << s << "\n";
        bool ind = true;
        while(s){
            used[s] = true;
            st.erase(s);
            pii B;
            if(x[u[s - 1]] == x[v[s - 1]]){
                B = mark_vertical_line(s);
                a[s - 1] = B.f, b[s -1] = B.s;
                s = 0;
            }
            else{
                B = mark_horizontal_line(s);
                a[s - 1] = B.f, b[s - 1] = B.s;
                s = 0;
            }
          //  cout << B.f << ' ' << B.s << "\n";
            pii pos[] = {{B.f - 1, B.s - 1}, {B.f + 1, B.s - 1}, {B.f - 1, B.s + 1}, {B.f + 1, B.s + 1}};
            for(int i = 0; i < 4; i++){
                for(int j = i + 1; j < 4; j++){
                    int o = mp[{pos[i], pos[j]}];
                    if(o && !used[o]){
                        s = o;
                        break;
                    }
                }
            }
        }
    }
    build(u, v, a, b);
    return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:101:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(int i = 1; i <= u.size(); i++)
      |                    ~~^~~~~~~~~~~
parks.cpp:107:14: warning: unused variable 'ind' [-Wunused-variable]
  107 |         bool ind = true;
      |              ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 2 ms 1876 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 1 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 1 ms 1876 KB Output is correct
8 Correct 2 ms 1908 KB Output is correct
9 Correct 655 ms 72320 KB Output is correct
10 Correct 28 ms 9080 KB Output is correct
11 Correct 191 ms 39776 KB Output is correct
12 Correct 46 ms 12720 KB Output is correct
13 Correct 72 ms 17388 KB Output is correct
14 Correct 3 ms 2132 KB Output is correct
15 Correct 4 ms 2516 KB Output is correct
16 Correct 654 ms 72300 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 2 ms 1876 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 1 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 1 ms 1876 KB Output is correct
8 Correct 2 ms 1908 KB Output is correct
9 Correct 655 ms 72320 KB Output is correct
10 Correct 28 ms 9080 KB Output is correct
11 Correct 191 ms 39776 KB Output is correct
12 Correct 46 ms 12720 KB Output is correct
13 Correct 72 ms 17388 KB Output is correct
14 Correct 3 ms 2132 KB Output is correct
15 Correct 4 ms 2516 KB Output is correct
16 Correct 654 ms 72300 KB Output is correct
17 Correct 1 ms 1876 KB Output is correct
18 Correct 1 ms 1876 KB Output is correct
19 Correct 2 ms 1876 KB Output is correct
20 Correct 1 ms 1904 KB Output is correct
21 Correct 1 ms 1832 KB Output is correct
22 Correct 1 ms 1876 KB Output is correct
23 Correct 1677 ms 121404 KB Output is correct
24 Correct 1 ms 1876 KB Output is correct
25 Correct 4 ms 2556 KB Output is correct
26 Correct 5 ms 2772 KB Output is correct
27 Correct 7 ms 3028 KB Output is correct
28 Correct 462 ms 49668 KB Output is correct
29 Correct 855 ms 73628 KB Output is correct
30 Correct 1425 ms 97432 KB Output is correct
31 Correct 1826 ms 121316 KB Output is correct
32 Correct 1 ms 1908 KB Output is correct
33 Correct 1 ms 1908 KB Output is correct
34 Correct 1 ms 1876 KB Output is correct
35 Correct 1 ms 1908 KB Output is correct
36 Correct 2 ms 1908 KB Output is correct
37 Correct 1 ms 1876 KB Output is correct
38 Correct 2 ms 1876 KB Output is correct
39 Correct 1 ms 1876 KB Output is correct
40 Correct 1 ms 1876 KB Output is correct
41 Correct 2 ms 1876 KB Output is correct
42 Correct 2 ms 1904 KB Output is correct
43 Correct 4 ms 2516 KB Output is correct
44 Correct 6 ms 2772 KB Output is correct
45 Correct 919 ms 66984 KB Output is correct
46 Correct 1497 ms 96240 KB Output is correct
47 Correct 1239 ms 96272 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 2 ms 1876 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 1 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 1 ms 1876 KB Output is correct
8 Correct 2 ms 1908 KB Output is correct
9 Correct 655 ms 72320 KB Output is correct
10 Correct 28 ms 9080 KB Output is correct
11 Correct 191 ms 39776 KB Output is correct
12 Correct 46 ms 12720 KB Output is correct
13 Correct 72 ms 17388 KB Output is correct
14 Correct 3 ms 2132 KB Output is correct
15 Correct 4 ms 2516 KB Output is correct
16 Correct 654 ms 72300 KB Output is correct
17 Correct 1 ms 1876 KB Output is correct
18 Correct 1 ms 1876 KB Output is correct
19 Correct 2 ms 1876 KB Output is correct
20 Correct 1 ms 1904 KB Output is correct
21 Correct 1 ms 1832 KB Output is correct
22 Correct 1 ms 1876 KB Output is correct
23 Correct 1677 ms 121404 KB Output is correct
24 Correct 1 ms 1876 KB Output is correct
25 Correct 4 ms 2556 KB Output is correct
26 Correct 5 ms 2772 KB Output is correct
27 Correct 7 ms 3028 KB Output is correct
28 Correct 462 ms 49668 KB Output is correct
29 Correct 855 ms 73628 KB Output is correct
30 Correct 1425 ms 97432 KB Output is correct
31 Correct 1826 ms 121316 KB Output is correct
32 Correct 1 ms 1908 KB Output is correct
33 Correct 1 ms 1908 KB Output is correct
34 Correct 1 ms 1876 KB Output is correct
35 Correct 1 ms 1908 KB Output is correct
36 Correct 2 ms 1908 KB Output is correct
37 Correct 1 ms 1876 KB Output is correct
38 Correct 2 ms 1876 KB Output is correct
39 Correct 1 ms 1876 KB Output is correct
40 Correct 1 ms 1876 KB Output is correct
41 Correct 2 ms 1876 KB Output is correct
42 Correct 2 ms 1904 KB Output is correct
43 Correct 4 ms 2516 KB Output is correct
44 Correct 6 ms 2772 KB Output is correct
45 Correct 919 ms 66984 KB Output is correct
46 Correct 1497 ms 96240 KB Output is correct
47 Correct 1239 ms 96272 KB Output is correct
48 Correct 1 ms 1904 KB Output is correct
49 Correct 1 ms 1876 KB Output is correct
50 Correct 1 ms 1876 KB Output is correct
51 Incorrect 1 ms 1876 KB Tree @(5, 5) appears more than once: for edges on positions 0 and 2
52 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 2 ms 1876 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 1 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 1 ms 1876 KB Output is correct
8 Correct 2 ms 1908 KB Output is correct
9 Correct 655 ms 72320 KB Output is correct
10 Correct 28 ms 9080 KB Output is correct
11 Correct 191 ms 39776 KB Output is correct
12 Correct 46 ms 12720 KB Output is correct
13 Correct 72 ms 17388 KB Output is correct
14 Correct 3 ms 2132 KB Output is correct
15 Correct 4 ms 2516 KB Output is correct
16 Correct 654 ms 72300 KB Output is correct
17 Correct 1 ms 1876 KB Output is correct
18 Correct 1 ms 1876 KB Output is correct
19 Correct 1 ms 1876 KB Output is correct
20 Correct 1421 ms 127108 KB Output is correct
21 Correct 1438 ms 114212 KB Output is correct
22 Correct 1500 ms 126688 KB Output is correct
23 Correct 1315 ms 122088 KB Output is correct
24 Correct 465 ms 45856 KB Output is correct
25 Correct 1045 ms 59816 KB Output is correct
26 Correct 803 ms 59900 KB Output is correct
27 Correct 1670 ms 130288 KB Output is correct
28 Correct 1616 ms 130412 KB Output is correct
29 Correct 1956 ms 130348 KB Output is correct
30 Correct 1851 ms 130448 KB Output is correct
31 Correct 1 ms 1876 KB Output is correct
32 Correct 56 ms 11008 KB Output is correct
33 Correct 180 ms 24296 KB Output is correct
34 Correct 1372 ms 114644 KB Output is correct
35 Correct 18 ms 4564 KB Output is correct
36 Correct 121 ms 15640 KB Output is correct
37 Correct 340 ms 29380 KB Output is correct
38 Correct 529 ms 49632 KB Output is correct
39 Correct 808 ms 67100 KB Output is correct
40 Correct 1187 ms 84980 KB Output is correct
41 Correct 1544 ms 103000 KB Output is correct
42 Correct 1929 ms 120712 KB Output is correct
43 Correct 1 ms 1876 KB Output is correct
44 Correct 1 ms 1908 KB Output is correct
45 Correct 1 ms 1876 KB Output is correct
46 Correct 1 ms 1876 KB Output is correct
47 Correct 1 ms 1876 KB Output is correct
48 Correct 1 ms 1876 KB Output is correct
49 Correct 1 ms 1876 KB Output is correct
50 Correct 1 ms 1904 KB Output is correct
51 Correct 1 ms 1876 KB Output is correct
52 Correct 1 ms 1876 KB Output is correct
53 Correct 1 ms 1876 KB Output is correct
54 Correct 4 ms 2424 KB Output is correct
55 Correct 5 ms 2772 KB Output is correct
56 Correct 749 ms 67020 KB Output is correct
57 Correct 1205 ms 96288 KB Output is correct
58 Correct 1268 ms 96372 KB Output is correct
59 Correct 1 ms 1904 KB Output is correct
60 Correct 1 ms 1876 KB Output is correct
61 Correct 1 ms 1908 KB Output is correct
62 Correct 1469 ms 136740 KB Output is correct
63 Correct 1527 ms 136568 KB Output is correct
64 Correct 1575 ms 135924 KB Output is correct
65 Correct 7 ms 3028 KB Output is correct
66 Correct 16 ms 4184 KB Output is correct
67 Correct 809 ms 64776 KB Output is correct
68 Correct 1325 ms 96452 KB Output is correct
69 Correct 1977 ms 127880 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 2 ms 1876 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 1 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 1 ms 1876 KB Output is correct
8 Correct 2 ms 1908 KB Output is correct
9 Correct 655 ms 72320 KB Output is correct
10 Correct 28 ms 9080 KB Output is correct
11 Correct 191 ms 39776 KB Output is correct
12 Correct 46 ms 12720 KB Output is correct
13 Correct 72 ms 17388 KB Output is correct
14 Correct 3 ms 2132 KB Output is correct
15 Correct 4 ms 2516 KB Output is correct
16 Correct 654 ms 72300 KB Output is correct
17 Correct 1522 ms 143504 KB Output is correct
18 Correct 1554 ms 143660 KB Output is correct
19 Correct 1457 ms 121872 KB Output is correct
20 Correct 1709 ms 111864 KB Output is correct
21 Correct 1532 ms 116120 KB Output is correct
22 Correct 1 ms 1876 KB Output is correct
23 Correct 158 ms 21508 KB Output is correct
24 Correct 43 ms 7252 KB Output is correct
25 Correct 205 ms 20428 KB Output is correct
26 Correct 479 ms 33600 KB Output is correct
27 Correct 759 ms 59816 KB Output is correct
28 Correct 1069 ms 74704 KB Output is correct
29 Correct 1312 ms 89252 KB Output is correct
30 Correct 1678 ms 103148 KB Output is correct
31 Correct 1828 ms 117964 KB Output is correct
32 Correct 1713 ms 128464 KB Output is correct
33 Correct 1438 ms 136580 KB Output is correct
34 Correct 9 ms 3280 KB Output is correct
35 Correct 16 ms 4524 KB Output is correct
36 Correct 704 ms 64428 KB Output is correct
37 Correct 1289 ms 95776 KB Output is correct
38 Correct 1925 ms 126960 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 2 ms 1876 KB Output is correct
4 Correct 1 ms 1876 KB Output is correct
5 Correct 1 ms 1876 KB Output is correct
6 Correct 1 ms 1876 KB Output is correct
7 Correct 1 ms 1876 KB Output is correct
8 Correct 2 ms 1908 KB Output is correct
9 Correct 655 ms 72320 KB Output is correct
10 Correct 28 ms 9080 KB Output is correct
11 Correct 191 ms 39776 KB Output is correct
12 Correct 46 ms 12720 KB Output is correct
13 Correct 72 ms 17388 KB Output is correct
14 Correct 3 ms 2132 KB Output is correct
15 Correct 4 ms 2516 KB Output is correct
16 Correct 654 ms 72300 KB Output is correct
17 Correct 1 ms 1876 KB Output is correct
18 Correct 1 ms 1876 KB Output is correct
19 Correct 2 ms 1876 KB Output is correct
20 Correct 1 ms 1904 KB Output is correct
21 Correct 1 ms 1832 KB Output is correct
22 Correct 1 ms 1876 KB Output is correct
23 Correct 1677 ms 121404 KB Output is correct
24 Correct 1 ms 1876 KB Output is correct
25 Correct 4 ms 2556 KB Output is correct
26 Correct 5 ms 2772 KB Output is correct
27 Correct 7 ms 3028 KB Output is correct
28 Correct 462 ms 49668 KB Output is correct
29 Correct 855 ms 73628 KB Output is correct
30 Correct 1425 ms 97432 KB Output is correct
31 Correct 1826 ms 121316 KB Output is correct
32 Correct 1 ms 1908 KB Output is correct
33 Correct 1 ms 1908 KB Output is correct
34 Correct 1 ms 1876 KB Output is correct
35 Correct 1 ms 1908 KB Output is correct
36 Correct 2 ms 1908 KB Output is correct
37 Correct 1 ms 1876 KB Output is correct
38 Correct 2 ms 1876 KB Output is correct
39 Correct 1 ms 1876 KB Output is correct
40 Correct 1 ms 1876 KB Output is correct
41 Correct 2 ms 1876 KB Output is correct
42 Correct 2 ms 1904 KB Output is correct
43 Correct 4 ms 2516 KB Output is correct
44 Correct 6 ms 2772 KB Output is correct
45 Correct 919 ms 66984 KB Output is correct
46 Correct 1497 ms 96240 KB Output is correct
47 Correct 1239 ms 96272 KB Output is correct
48 Correct 1 ms 1904 KB Output is correct
49 Correct 1 ms 1876 KB Output is correct
50 Correct 1 ms 1876 KB Output is correct
51 Incorrect 1 ms 1876 KB Tree @(5, 5) appears more than once: for edges on positions 0 and 2
52 Halted 0 ms 0 KB -