oj.uz

Submission #446955

# Submission time Handle Problem Language Result Execution time Memory
446955 2021-07-24T05:06:13 Z blue Fountain Parks (IOI21_parks) C++17
55 / 100
 1109 ms 117396 KB 
#include "parks.h"
#include <vector>
#include <set>
#include <algorithm>
#include <iostream>
using namespace std;

const int maxN = 200'000;
const int MX = 1'000'000;



vector<int> fountain_edge[maxN];
vector<int> fountain_visit(maxN, 0);
int visit_count = 0;

void fountain_dfs(int u)
{
    fountain_visit[u] = 1;
    visit_count++;
    for(int v: fountain_edge[u])
    {
        if(fountain_visit[v]) continue;
        fountain_dfs(v);
    }
}






struct point
{
    int i;
    int x;
    int y;
};

bool operator < (point A, point B)
{
    if(A.x == B.x) return A.y < B.y;
    return A.x < B.x;
};


int N;
vector<int> X, Y;
set<point> fountains;

int point_index(int x, int y)
{
    set<point>::iterator it = fountains.find(point{-1, x, y});
    if(it == fountains.end()) return -1;
    else return it->i;
}





struct path
{
    int i;
    int a;
    int b;

    path(int A, int B)
    {
        a = min(A, B);
        b = max(A, B);
    }

    path(int I, int A, int B)
    {
        i = I;
        a = min(A, B);
        b = max(A, B);
    }
};

bool operator < (path P, path Q)
{
    if(P.a == Q.a) return P.b < Q.b;
    return P.a < Q.a;
}

vector<path> temp_paths;
set<path> paths;





struct bench
{
    int i;
    int x;
    int y;
};

bool operator < (bench C, bench D)
{
    if(C.x == D.x) return C.y < D.y;
    return C.x < D.x;
}


set<bench> benches;

int bench_index(int x, int y)
{
    set<bench>::iterator it = benches.find(bench{-1, x, y});
    if(it == benches.end()) return -1;
    else return it->i;
}


vector<path>* bench_edge = new vector<path>[MX];











vector<int> bench_visit(MX, 0);

vector<int> U, V, A, B;










vector<int> parent(maxN);
vector<int> siz(maxN, 1);


int getRoot(int u)
{
    int v;
    for(v = u; parent[v] != v; v = parent[v]);
    parent[u] = v;
    return v;
}

void join(int u, int v)
{
    u = getRoot(u);
    v = getRoot(v);

    if(siz[u] < siz[v]) swap(u, v);

    parent[v] = u;
    siz[u] += siz[v];
}

bool connected(int u, int v)
{
    return getRoot(u) == getRoot(v);
}








int construct_roads(vector<int> x, vector<int> y)
{
    // cerr << "check\n";
    X = x;
    Y = y;

    N = X.size();

    for(int i = 0; i < N; i++)
        fountains.insert(point{i, x[i], y[i]});







    // cerr << "check 2\n";


    for(int i = 0; i < N; i++)
    {
        int I;

        I = point_index(x[i] - 2, y[i]);
        if(I != -1)
        {
            // cerr << i << ' ' << I << '\n';

            fountain_edge[i].push_back(I);
            fountain_edge[I].push_back(i);

            temp_paths.push_back(path(i, I));

            // cerr << temp_paths.size() << '\n';
        }

        I = point_index(x[i], y[i] - 2);
        if(I != -1)
        {
            // cerr << i << ' ' << I << '\n';

            fountain_edge[i].push_back(I);
            fountain_edge[I].push_back(i);

            temp_paths.push_back(path(i, I));

            // cerr << temp_paths.size() << '\n';
        }
    }

    // cerr << temp_paths.size() << '\n';

    // cerr << "check 3\n";






    fountain_dfs(0);
    if(visit_count != N)
    {
        return 0;
    }





    int path_id = -1;
    for(path p: temp_paths)
    {
        path_id++;
            // cerr << "P -> " << path_id << ' ' << p.a <<  ' ' << p.b << '\n';
        paths.insert(path(path_id, p.a, p.b));
    }

    // cerr << "check 4\n";







    int bench_id = -1;
    for(path p: paths)
    {
        // cerr << "p = " << p.i << ' ' << p.a << ' ' << p.b << '\n';
        int x1 = X[p.a];
        int y1 = Y[p.a];

        int x2 = X[p.b];
        int y2 = Y[p.b];


        bench new_bench;

        if(x1 == x2)
        {
            if( ((x1+1) + (y1+y2)/2) % 4 == 0 )
                new_bench = bench{-1, x1+1, (y1+y2)/2};
            else
                new_bench = bench{-1, x1-1, (y1+y2)/2};
        }
        else
        {
            if( ((x1+x2)/2 + (y1+1)) % 4 == 2 )
                new_bench = bench{-1, (x1+x2)/2, y1+1};
            else
                new_bench = bench{-1, (x1+x2)/2, y1-1};
        }

        int curr_bench_index;

        // cerr << "before I\n";

        int I = bench_index(new_bench.x, new_bench.y);

        if(I == -1)
        {
            bench_id++;
            curr_bench_index = bench_id;

            new_bench.i = curr_bench_index;

            benches.insert(new_bench);
        }
        else
        {
            curr_bench_index = I;
        }

        bench_edge[curr_bench_index].push_back(p);
    }

    // cerr << "check 5\n";









    for(int i = 0; i < N; i++)
        parent[i] = i;


    for(int i = 0; i <= bench_id; i++)
    {
        sort(bench_edge[i].begin(), bench_edge[i].end(), [] (path P1, path P2)
        {
            if(X[P1.a] == X[P1.b]) return Y[P1.a] < Y[P1.b];
            else return X[P1.a] < X[P1.b];
        });
    }

    // cerr << "check 6\n";



    for(bench q: benches)
    {
        for(path z: bench_edge[q.i])
        {
            if(connected(z.a, z.b)) continue;

            U.push_back(z.a);
            V.push_back(z.b);
            A.push_back(q.x);
            B.push_back(q.y);

            join(z.a, z.b);

            break;
        }
    }

    // cerr << "check 7\n";

    build(U, V, A, B);
    return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 34740 KB Output is correct
2 Correct 17 ms 34636 KB Output is correct
3 Correct 18 ms 34716 KB Output is correct
4 Correct 17 ms 34764 KB Output is correct
5 Correct 17 ms 34728 KB Output is correct
6 Correct 16 ms 34636 KB Output is correct
7 Correct 18 ms 34712 KB Output is correct
8 Correct 20 ms 34656 KB Output is correct
9 Correct 319 ms 72484 KB Output is correct
10 Correct 34 ms 38684 KB Output is correct
11 Correct 130 ms 55028 KB Output is correct
12 Correct 43 ms 40396 KB Output is correct
13 Correct 52 ms 41340 KB Output is correct
14 Correct 18 ms 34892 KB Output is correct
15 Correct 18 ms 35024 KB Output is correct
16 Correct 315 ms 71160 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 34740 KB Output is correct
2 Correct 17 ms 34636 KB Output is correct
3 Correct 18 ms 34716 KB Output is correct
4 Correct 17 ms 34764 KB Output is correct
5 Correct 17 ms 34728 KB Output is correct
6 Correct 16 ms 34636 KB Output is correct
7 Correct 18 ms 34712 KB Output is correct
8 Correct 20 ms 34656 KB Output is correct
9 Correct 319 ms 72484 KB Output is correct
10 Correct 34 ms 38684 KB Output is correct
11 Correct 130 ms 55028 KB Output is correct
12 Correct 43 ms 40396 KB Output is correct
13 Correct 52 ms 41340 KB Output is correct
14 Correct 18 ms 34892 KB Output is correct
15 Correct 18 ms 35024 KB Output is correct
16 Correct 315 ms 71160 KB Output is correct
17 Correct 17 ms 34764 KB Output is correct
18 Correct 17 ms 34764 KB Output is correct
19 Correct 17 ms 34660 KB Output is correct
20 Correct 17 ms 34660 KB Output is correct
21 Correct 18 ms 34728 KB Output is correct
22 Correct 18 ms 34636 KB Output is correct
23 Correct 1006 ms 116752 KB Output is correct
24 Correct 17 ms 34764 KB Output is correct
25 Correct 19 ms 35168 KB Output is correct
26 Correct 20 ms 35180 KB Output is correct
27 Correct 19 ms 35268 KB Output is correct
28 Correct 366 ms 67916 KB Output is correct
29 Correct 511 ms 82944 KB Output is correct
30 Correct 771 ms 100888 KB Output is correct
31 Correct 1062 ms 116376 KB Output is correct
32 Correct 17 ms 34720 KB Output is correct
33 Correct 17 ms 34764 KB Output is correct
34 Correct 17 ms 34680 KB Output is correct
35 Correct 17 ms 34756 KB Output is correct
36 Correct 16 ms 34704 KB Output is correct
37 Correct 17 ms 34764 KB Output is correct
38 Correct 17 ms 34636 KB Output is correct
39 Correct 17 ms 34764 KB Output is correct
40 Correct 17 ms 34696 KB Output is correct
41 Correct 17 ms 34764 KB Output is correct
42 Correct 17 ms 34664 KB Output is correct
43 Correct 18 ms 34992 KB Output is correct
44 Correct 20 ms 35028 KB Output is correct
45 Correct 330 ms 71544 KB Output is correct
46 Correct 532 ms 89292 KB Output is correct
47 Correct 549 ms 89120 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 34740 KB Output is correct
2 Correct 17 ms 34636 KB Output is correct
3 Correct 18 ms 34716 KB Output is correct
4 Correct 17 ms 34764 KB Output is correct
5 Correct 17 ms 34728 KB Output is correct
6 Correct 16 ms 34636 KB Output is correct
7 Correct 18 ms 34712 KB Output is correct
8 Correct 20 ms 34656 KB Output is correct
9 Correct 319 ms 72484 KB Output is correct
10 Correct 34 ms 38684 KB Output is correct
11 Correct 130 ms 55028 KB Output is correct
12 Correct 43 ms 40396 KB Output is correct
13 Correct 52 ms 41340 KB Output is correct
14 Correct 18 ms 34892 KB Output is correct
15 Correct 18 ms 35024 KB Output is correct
16 Correct 315 ms 71160 KB Output is correct
17 Correct 17 ms 34764 KB Output is correct
18 Correct 17 ms 34764 KB Output is correct
19 Correct 17 ms 34660 KB Output is correct
20 Correct 17 ms 34660 KB Output is correct
21 Correct 18 ms 34728 KB Output is correct
22 Correct 18 ms 34636 KB Output is correct
23 Correct 1006 ms 116752 KB Output is correct
24 Correct 17 ms 34764 KB Output is correct
25 Correct 19 ms 35168 KB Output is correct
26 Correct 20 ms 35180 KB Output is correct
27 Correct 19 ms 35268 KB Output is correct
28 Correct 366 ms 67916 KB Output is correct
29 Correct 511 ms 82944 KB Output is correct
30 Correct 771 ms 100888 KB Output is correct
31 Correct 1062 ms 116376 KB Output is correct
32 Correct 17 ms 34720 KB Output is correct
33 Correct 17 ms 34764 KB Output is correct
34 Correct 17 ms 34680 KB Output is correct
35 Correct 17 ms 34756 KB Output is correct
36 Correct 16 ms 34704 KB Output is correct
37 Correct 17 ms 34764 KB Output is correct
38 Correct 17 ms 34636 KB Output is correct
39 Correct 17 ms 34764 KB Output is correct
40 Correct 17 ms 34696 KB Output is correct
41 Correct 17 ms 34764 KB Output is correct
42 Correct 17 ms 34664 KB Output is correct
43 Correct 18 ms 34992 KB Output is correct
44 Correct 20 ms 35028 KB Output is correct
45 Correct 330 ms 71544 KB Output is correct
46 Correct 532 ms 89292 KB Output is correct
47 Correct 549 ms 89120 KB Output is correct
48 Correct 17 ms 34660 KB Output is correct
49 Correct 17 ms 34764 KB Output is correct
50 Correct 17 ms 34636 KB Output is correct
51 Correct 17 ms 34764 KB Output is correct
52 Correct 18 ms 34732 KB Output is correct
53 Correct 17 ms 34692 KB Output is correct
54 Correct 17 ms 34640 KB Output is correct
55 Incorrect 1109 ms 117396 KB Given structure is not connected: There is no path between vertices 0 and 110
56 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 34740 KB Output is correct
2 Correct 17 ms 34636 KB Output is correct
3 Correct 18 ms 34716 KB Output is correct
4 Correct 17 ms 34764 KB Output is correct
5 Correct 17 ms 34728 KB Output is correct
6 Correct 16 ms 34636 KB Output is correct
7 Correct 18 ms 34712 KB Output is correct
8 Correct 20 ms 34656 KB Output is correct
9 Correct 319 ms 72484 KB Output is correct
10 Correct 34 ms 38684 KB Output is correct
11 Correct 130 ms 55028 KB Output is correct
12 Correct 43 ms 40396 KB Output is correct
13 Correct 52 ms 41340 KB Output is correct
14 Correct 18 ms 34892 KB Output is correct
15 Correct 18 ms 35024 KB Output is correct
16 Correct 315 ms 71160 KB Output is correct
17 Correct 17 ms 34636 KB Output is correct
18 Correct 17 ms 34636 KB Output is correct
19 Correct 17 ms 34764 KB Output is correct
20 Correct 791 ms 111712 KB Output is correct
21 Correct 793 ms 110420 KB Output is correct
22 Correct 866 ms 109652 KB Output is correct
23 Correct 645 ms 98448 KB Output is correct
24 Correct 257 ms 51968 KB Output is correct
25 Correct 420 ms 60552 KB Output is correct
26 Correct 388 ms 60520 KB Output is correct
27 Correct 840 ms 104632 KB Output is correct
28 Correct 809 ms 104732 KB Output is correct
29 Correct 811 ms 104788 KB Output is correct
30 Correct 845 ms 104788 KB Output is correct
31 Correct 17 ms 34636 KB Output is correct
32 Correct 47 ms 39992 KB Output is correct
33 Correct 97 ms 43292 KB Output is correct
34 Correct 763 ms 110648 KB Output is correct
35 Correct 26 ms 36044 KB Output is correct
36 Correct 75 ms 41088 KB Output is correct
37 Correct 168 ms 47580 KB Output is correct
38 Correct 270 ms 63332 KB Output is correct
39 Correct 406 ms 73512 KB Output is correct
40 Correct 572 ms 85288 KB Output is correct
41 Correct 727 ms 95388 KB Output is correct
42 Correct 949 ms 105592 KB Output is correct
43 Correct 16 ms 34764 KB Output is correct
44 Correct 17 ms 34744 KB Output is correct
45 Correct 17 ms 34688 KB Output is correct
46 Correct 17 ms 34636 KB Output is correct
47 Correct 17 ms 34636 KB Output is correct
48 Correct 17 ms 34764 KB Output is correct
49 Correct 17 ms 34760 KB Output is correct
50 Correct 17 ms 34676 KB Output is correct
51 Correct 17 ms 34636 KB Output is correct
52 Correct 18 ms 34644 KB Output is correct
53 Correct 17 ms 34744 KB Output is correct
54 Correct 19 ms 35024 KB Output is correct
55 Correct 19 ms 35148 KB Output is correct
56 Correct 310 ms 71528 KB Output is correct
57 Correct 573 ms 89220 KB Output is correct
58 Correct 529 ms 89124 KB Output is correct
59 Correct 17 ms 34764 KB Output is correct
60 Correct 18 ms 34732 KB Output is correct
61 Correct 17 ms 34740 KB Output is correct
62 Correct 745 ms 109076 KB Output is correct
63 Correct 766 ms 109264 KB Output is correct
64 Correct 769 ms 109568 KB Output is correct
65 Correct 20 ms 35248 KB Output is correct
66 Correct 23 ms 35752 KB Output is correct
67 Correct 350 ms 70528 KB Output is correct
68 Correct 606 ms 90272 KB Output is correct
69 Correct 837 ms 106888 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 34740 KB Output is correct
2 Correct 17 ms 34636 KB Output is correct
3 Correct 18 ms 34716 KB Output is correct
4 Correct 17 ms 34764 KB Output is correct
5 Correct 17 ms 34728 KB Output is correct
6 Correct 16 ms 34636 KB Output is correct
7 Correct 18 ms 34712 KB Output is correct
8 Correct 20 ms 34656 KB Output is correct
9 Correct 319 ms 72484 KB Output is correct
10 Correct 34 ms 38684 KB Output is correct
11 Correct 130 ms 55028 KB Output is correct
12 Correct 43 ms 40396 KB Output is correct
13 Correct 52 ms 41340 KB Output is correct
14 Correct 18 ms 34892 KB Output is correct
15 Correct 18 ms 35024 KB Output is correct
16 Correct 315 ms 71160 KB Output is correct
17 Correct 808 ms 111476 KB Output is correct
18 Correct 789 ms 111060 KB Output is correct
19 Correct 779 ms 111604 KB Output is correct
20 Correct 972 ms 116464 KB Output is correct
21 Correct 735 ms 101268 KB Output is correct
22 Correct 17 ms 34764 KB Output is correct
23 Correct 101 ms 46564 KB Output is correct
24 Correct 38 ms 37396 KB Output is correct
25 Correct 108 ms 44312 KB Output is correct
26 Correct 235 ms 51856 KB Output is correct
27 Correct 372 ms 74356 KB Output is correct
28 Correct 500 ms 84272 KB Output is correct
29 Correct 666 ms 95136 KB Output is correct
30 Correct 818 ms 104532 KB Output is correct
31 Correct 937 ms 114376 KB Output is correct
32 Correct 920 ms 115028 KB Output is correct
33 Correct 763 ms 112660 KB Output is correct
34 Correct 21 ms 35532 KB Output is correct
35 Correct 26 ms 36068 KB Output is correct
36 Correct 342 ms 73668 KB Output is correct
37 Correct 577 ms 94340 KB Output is correct
38 Correct 873 ms 113248 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 34740 KB Output is correct
2 Correct 17 ms 34636 KB Output is correct
3 Correct 18 ms 34716 KB Output is correct
4 Correct 17 ms 34764 KB Output is correct
5 Correct 17 ms 34728 KB Output is correct
6 Correct 16 ms 34636 KB Output is correct
7 Correct 18 ms 34712 KB Output is correct
8 Correct 20 ms 34656 KB Output is correct
9 Correct 319 ms 72484 KB Output is correct
10 Correct 34 ms 38684 KB Output is correct
11 Correct 130 ms 55028 KB Output is correct
12 Correct 43 ms 40396 KB Output is correct
13 Correct 52 ms 41340 KB Output is correct
14 Correct 18 ms 34892 KB Output is correct
15 Correct 18 ms 35024 KB Output is correct
16 Correct 315 ms 71160 KB Output is correct
17 Correct 17 ms 34764 KB Output is correct
18 Correct 17 ms 34764 KB Output is correct
19 Correct 17 ms 34660 KB Output is correct
20 Correct 17 ms 34660 KB Output is correct
21 Correct 18 ms 34728 KB Output is correct
22 Correct 18 ms 34636 KB Output is correct
23 Correct 1006 ms 116752 KB Output is correct
24 Correct 17 ms 34764 KB Output is correct
25 Correct 19 ms 35168 KB Output is correct
26 Correct 20 ms 35180 KB Output is correct
27 Correct 19 ms 35268 KB Output is correct
28 Correct 366 ms 67916 KB Output is correct
29 Correct 511 ms 82944 KB Output is correct
30 Correct 771 ms 100888 KB Output is correct
31 Correct 1062 ms 116376 KB Output is correct
32 Correct 17 ms 34720 KB Output is correct
33 Correct 17 ms 34764 KB Output is correct
34 Correct 17 ms 34680 KB Output is correct
35 Correct 17 ms 34756 KB Output is correct
36 Correct 16 ms 34704 KB Output is correct
37 Correct 17 ms 34764 KB Output is correct
38 Correct 17 ms 34636 KB Output is correct
39 Correct 17 ms 34764 KB Output is correct
40 Correct 17 ms 34696 KB Output is correct
41 Correct 17 ms 34764 KB Output is correct
42 Correct 17 ms 34664 KB Output is correct
43 Correct 18 ms 34992 KB Output is correct
44 Correct 20 ms 35028 KB Output is correct
45 Correct 330 ms 71544 KB Output is correct
46 Correct 532 ms 89292 KB Output is correct
47 Correct 549 ms 89120 KB Output is correct
48 Correct 17 ms 34660 KB Output is correct
49 Correct 17 ms 34764 KB Output is correct
50 Correct 17 ms 34636 KB Output is correct
51 Correct 17 ms 34764 KB Output is correct
52 Correct 18 ms 34732 KB Output is correct
53 Correct 17 ms 34692 KB Output is correct
54 Correct 17 ms 34640 KB Output is correct
55 Incorrect 1109 ms 117396 KB Given structure is not connected: There is no path between vertices 0 and 110
56 Halted 0 ms 0 KB -