oj.uz

Submission #446950

# Submission time Handle Problem Language Result Execution time Memory
446950 2021-07-24T04:57:04 Z blue Fountain Parks (IOI21_parks) C++17
35 / 100
 3500 ms 132712 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;
}

set<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;
}

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.insert(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.insert(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 == 2 )
                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 == 0 )
                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 34636 KB Output is correct
2 Correct 17 ms 34764 KB Output is correct
3 Correct 17 ms 34656 KB Output is correct
4 Correct 17 ms 34764 KB Output is correct
5 Correct 18 ms 34764 KB Output is correct
6 Correct 17 ms 34680 KB Output is correct
7 Correct 17 ms 34772 KB Output is correct
8 Correct 17 ms 34764 KB Output is correct
9 Correct 397 ms 76148 KB Output is correct
10 Correct 36 ms 39108 KB Output is correct
11 Correct 148 ms 57284 KB Output is correct
12 Correct 46 ms 41220 KB Output is correct
13 Correct 65 ms 43588 KB Output is correct
14 Correct 18 ms 34892 KB Output is correct
15 Correct 18 ms 35092 KB Output is correct
16 Correct 394 ms 74904 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 34636 KB Output is correct
2 Correct 17 ms 34764 KB Output is correct
3 Correct 17 ms 34656 KB Output is correct
4 Correct 17 ms 34764 KB Output is correct
5 Correct 18 ms 34764 KB Output is correct
6 Correct 17 ms 34680 KB Output is correct
7 Correct 17 ms 34772 KB Output is correct
8 Correct 17 ms 34764 KB Output is correct
9 Correct 397 ms 76148 KB Output is correct
10 Correct 36 ms 39108 KB Output is correct
11 Correct 148 ms 57284 KB Output is correct
12 Correct 46 ms 41220 KB Output is correct
13 Correct 65 ms 43588 KB Output is correct
14 Correct 18 ms 34892 KB Output is correct
15 Correct 18 ms 35092 KB Output is correct
16 Correct 394 ms 74904 KB Output is correct
17 Correct 17 ms 34764 KB Output is correct
18 Correct 17 ms 34740 KB Output is correct
19 Correct 17 ms 34692 KB Output is correct
20 Correct 17 ms 34636 KB Output is correct
21 Correct 17 ms 34760 KB Output is correct
22 Correct 17 ms 34676 KB Output is correct
23 Correct 1238 ms 130332 KB Output is correct
24 Correct 17 ms 34664 KB Output is correct
25 Correct 20 ms 35280 KB Output is correct
26 Correct 20 ms 35412 KB Output is correct
27 Correct 21 ms 35544 KB Output is correct
28 Correct 372 ms 73332 KB Output is correct
29 Correct 652 ms 91568 KB Output is correct
30 Correct 950 ms 111080 KB Output is correct
31 Correct 1279 ms 129976 KB Output is correct
32 Correct 17 ms 34764 KB Output is correct
33 Correct 18 ms 34640 KB Output is correct
34 Correct 17 ms 34660 KB Output is correct
35 Correct 17 ms 34772 KB Output is correct
36 Correct 17 ms 34764 KB Output is correct
37 Correct 19 ms 34688 KB Output is correct
38 Correct 19 ms 34764 KB Output is correct
39 Correct 17 ms 34672 KB Output is correct
40 Correct 19 ms 34636 KB Output is correct
41 Correct 17 ms 34648 KB Output is correct
42 Correct 17 ms 34744 KB Output is correct
43 Correct 22 ms 35032 KB Output is correct
44 Correct 20 ms 35236 KB Output is correct
45 Correct 448 ms 76060 KB Output is correct
46 Correct 674 ms 94640 KB Output is correct
47 Correct 692 ms 94500 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 34636 KB Output is correct
2 Correct 17 ms 34764 KB Output is correct
3 Correct 17 ms 34656 KB Output is correct
4 Correct 17 ms 34764 KB Output is correct
5 Correct 18 ms 34764 KB Output is correct
6 Correct 17 ms 34680 KB Output is correct
7 Correct 17 ms 34772 KB Output is correct
8 Correct 17 ms 34764 KB Output is correct
9 Correct 397 ms 76148 KB Output is correct
10 Correct 36 ms 39108 KB Output is correct
11 Correct 148 ms 57284 KB Output is correct
12 Correct 46 ms 41220 KB Output is correct
13 Correct 65 ms 43588 KB Output is correct
14 Correct 18 ms 34892 KB Output is correct
15 Correct 18 ms 35092 KB Output is correct
16 Correct 394 ms 74904 KB Output is correct
17 Correct 17 ms 34764 KB Output is correct
18 Correct 17 ms 34740 KB Output is correct
19 Correct 17 ms 34692 KB Output is correct
20 Correct 17 ms 34636 KB Output is correct
21 Correct 17 ms 34760 KB Output is correct
22 Correct 17 ms 34676 KB Output is correct
23 Correct 1238 ms 130332 KB Output is correct
24 Correct 17 ms 34664 KB Output is correct
25 Correct 20 ms 35280 KB Output is correct
26 Correct 20 ms 35412 KB Output is correct
27 Correct 21 ms 35544 KB Output is correct
28 Correct 372 ms 73332 KB Output is correct
29 Correct 652 ms 91568 KB Output is correct
30 Correct 950 ms 111080 KB Output is correct
31 Correct 1279 ms 129976 KB Output is correct
32 Correct 17 ms 34764 KB Output is correct
33 Correct 18 ms 34640 KB Output is correct
34 Correct 17 ms 34660 KB Output is correct
35 Correct 17 ms 34772 KB Output is correct
36 Correct 17 ms 34764 KB Output is correct
37 Correct 19 ms 34688 KB Output is correct
38 Correct 19 ms 34764 KB Output is correct
39 Correct 17 ms 34672 KB Output is correct
40 Correct 19 ms 34636 KB Output is correct
41 Correct 17 ms 34648 KB Output is correct
42 Correct 17 ms 34744 KB Output is correct
43 Correct 22 ms 35032 KB Output is correct
44 Correct 20 ms 35236 KB Output is correct
45 Correct 448 ms 76060 KB Output is correct
46 Correct 674 ms 94640 KB Output is correct
47 Correct 692 ms 94500 KB Output is correct
48 Correct 19 ms 34720 KB Output is correct
49 Correct 17 ms 34652 KB Output is correct
50 Correct 19 ms 34688 KB Output is correct
51 Correct 18 ms 34764 KB Output is correct
52 Correct 18 ms 34760 KB Output is correct
53 Correct 17 ms 34764 KB Output is correct
54 Correct 17 ms 34720 KB Output is correct
55 Incorrect 1335 ms 132712 KB Given structure is not connected: There is no path between vertices 0 and 55
56 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 34636 KB Output is correct
2 Correct 17 ms 34764 KB Output is correct
3 Correct 17 ms 34656 KB Output is correct
4 Correct 17 ms 34764 KB Output is correct
5 Correct 18 ms 34764 KB Output is correct
6 Correct 17 ms 34680 KB Output is correct
7 Correct 17 ms 34772 KB Output is correct
8 Correct 17 ms 34764 KB Output is correct
9 Correct 397 ms 76148 KB Output is correct
10 Correct 36 ms 39108 KB Output is correct
11 Correct 148 ms 57284 KB Output is correct
12 Correct 46 ms 41220 KB Output is correct
13 Correct 65 ms 43588 KB Output is correct
14 Correct 18 ms 34892 KB Output is correct
15 Correct 18 ms 35092 KB Output is correct
16 Correct 394 ms 74904 KB Output is correct
17 Correct 16 ms 34636 KB Output is correct
18 Correct 17 ms 34676 KB Output is correct
19 Correct 18 ms 34700 KB Output is correct
20 Correct 970 ms 118416 KB Output is correct
21 Correct 980 ms 116792 KB Output is correct
22 Correct 977 ms 116144 KB Output is correct
23 Correct 796 ms 103616 KB Output is correct
24 Correct 237 ms 51908 KB Output is correct
25 Correct 626 ms 70624 KB Output is correct
26 Correct 531 ms 70644 KB Output is correct
27 Correct 961 ms 111564 KB Output is correct
28 Correct 1008 ms 111688 KB Output is correct
29 Correct 1279 ms 111712 KB Output is correct
30 Correct 1065 ms 111632 KB Output is correct
31 Correct 17 ms 34764 KB Output is correct
32 Correct 53 ms 40668 KB Output is correct
33 Correct 99 ms 43332 KB Output is correct
34 Correct 981 ms 117264 KB Output is correct
35 Correct 28 ms 36452 KB Output is correct
36 Correct 125 ms 43708 KB Output is correct
37 Correct 252 ms 52700 KB Output is correct
38 Correct 322 ms 65708 KB Output is correct
39 Correct 456 ms 77324 KB Output is correct
40 Correct 685 ms 88856 KB Output is correct
41 Correct 890 ms 100560 KB Output is correct
42 Correct 1036 ms 112160 KB Output is correct
43 Correct 19 ms 34660 KB Output is correct
44 Correct 17 ms 34636 KB Output is correct
45 Correct 19 ms 34708 KB Output is correct
46 Correct 16 ms 34692 KB Output is correct
47 Correct 16 ms 34728 KB Output is correct
48 Correct 18 ms 34656 KB Output is correct
49 Correct 17 ms 34708 KB Output is correct
50 Correct 17 ms 34756 KB Output is correct
51 Correct 17 ms 34636 KB Output is correct
52 Correct 17 ms 34636 KB Output is correct
53 Correct 17 ms 34740 KB Output is correct
54 Correct 19 ms 35024 KB Output is correct
55 Correct 20 ms 35288 KB Output is correct
56 Correct 409 ms 75180 KB Output is correct
57 Correct 646 ms 93468 KB Output is correct
58 Correct 629 ms 93308 KB Output is correct
59 Correct 17 ms 34636 KB Output is correct
60 Correct 18 ms 34696 KB Output is correct
61 Correct 17 ms 34748 KB Output is correct
62 Correct 979 ms 116024 KB Output is correct
63 Correct 930 ms 116072 KB Output is correct
64 Correct 920 ms 116500 KB Output is correct
65 Correct 21 ms 35532 KB Output is correct
66 Correct 26 ms 36112 KB Output is correct
67 Correct 402 ms 74192 KB Output is correct
68 Correct 732 ms 94724 KB Output is correct
69 Correct 1014 ms 113740 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 34636 KB Output is correct
2 Correct 17 ms 34764 KB Output is correct
3 Correct 17 ms 34656 KB Output is correct
4 Correct 17 ms 34764 KB Output is correct
5 Correct 18 ms 34764 KB Output is correct
6 Correct 17 ms 34680 KB Output is correct
7 Correct 17 ms 34772 KB Output is correct
8 Correct 17 ms 34764 KB Output is correct
9 Correct 397 ms 76148 KB Output is correct
10 Correct 36 ms 39108 KB Output is correct
11 Correct 148 ms 57284 KB Output is correct
12 Correct 46 ms 41220 KB Output is correct
13 Correct 65 ms 43588 KB Output is correct
14 Correct 18 ms 34892 KB Output is correct
15 Correct 18 ms 35092 KB Output is correct
16 Correct 394 ms 74904 KB Output is correct
17 Correct 1006 ms 117872 KB Output is correct
18 Correct 927 ms 117372 KB Output is correct
19 Correct 1039 ms 118332 KB Output is correct
20 Correct 1230 ms 126496 KB Output is correct
21 Correct 944 ms 107864 KB Output is correct
22 Correct 17 ms 34636 KB Output is correct
23 Correct 110 ms 48280 KB Output is correct
24 Correct 46 ms 38596 KB Output is correct
25 Correct 152 ms 48292 KB Output is correct
26 Correct 318 ms 57796 KB Output is correct
27 Correct 503 ms 78720 KB Output is correct
28 Correct 612 ms 89892 KB Output is correct
29 Correct 815 ms 100800 KB Output is correct
30 Correct 1044 ms 111500 KB Output is correct
31 Correct 1168 ms 122800 KB Output is correct
32 Execution timed out 3590 ms 117204 KB Time limit exceeded
33 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 34636 KB Output is correct
2 Correct 17 ms 34764 KB Output is correct
3 Correct 17 ms 34656 KB Output is correct
4 Correct 17 ms 34764 KB Output is correct
5 Correct 18 ms 34764 KB Output is correct
6 Correct 17 ms 34680 KB Output is correct
7 Correct 17 ms 34772 KB Output is correct
8 Correct 17 ms 34764 KB Output is correct
9 Correct 397 ms 76148 KB Output is correct
10 Correct 36 ms 39108 KB Output is correct
11 Correct 148 ms 57284 KB Output is correct
12 Correct 46 ms 41220 KB Output is correct
13 Correct 65 ms 43588 KB Output is correct
14 Correct 18 ms 34892 KB Output is correct
15 Correct 18 ms 35092 KB Output is correct
16 Correct 394 ms 74904 KB Output is correct
17 Correct 17 ms 34764 KB Output is correct
18 Correct 17 ms 34740 KB Output is correct
19 Correct 17 ms 34692 KB Output is correct
20 Correct 17 ms 34636 KB Output is correct
21 Correct 17 ms 34760 KB Output is correct
22 Correct 17 ms 34676 KB Output is correct
23 Correct 1238 ms 130332 KB Output is correct
24 Correct 17 ms 34664 KB Output is correct
25 Correct 20 ms 35280 KB Output is correct
26 Correct 20 ms 35412 KB Output is correct
27 Correct 21 ms 35544 KB Output is correct
28 Correct 372 ms 73332 KB Output is correct
29 Correct 652 ms 91568 KB Output is correct
30 Correct 950 ms 111080 KB Output is correct
31 Correct 1279 ms 129976 KB Output is correct
32 Correct 17 ms 34764 KB Output is correct
33 Correct 18 ms 34640 KB Output is correct
34 Correct 17 ms 34660 KB Output is correct
35 Correct 17 ms 34772 KB Output is correct
36 Correct 17 ms 34764 KB Output is correct
37 Correct 19 ms 34688 KB Output is correct
38 Correct 19 ms 34764 KB Output is correct
39 Correct 17 ms 34672 KB Output is correct
40 Correct 19 ms 34636 KB Output is correct
41 Correct 17 ms 34648 KB Output is correct
42 Correct 17 ms 34744 KB Output is correct
43 Correct 22 ms 35032 KB Output is correct
44 Correct 20 ms 35236 KB Output is correct
45 Correct 448 ms 76060 KB Output is correct
46 Correct 674 ms 94640 KB Output is correct
47 Correct 692 ms 94500 KB Output is correct
48 Correct 19 ms 34720 KB Output is correct
49 Correct 17 ms 34652 KB Output is correct
50 Correct 19 ms 34688 KB Output is correct
51 Correct 18 ms 34764 KB Output is correct
52 Correct 18 ms 34760 KB Output is correct
53 Correct 17 ms 34764 KB Output is correct
54 Correct 17 ms 34720 KB Output is correct
55 Incorrect 1335 ms 132712 KB Given structure is not connected: There is no path between vertices 0 and 55
56 Halted 0 ms 0 KB -