oj.uz

Submission #446951

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

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 == 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 16 ms 34636 KB Output is correct
2 Correct 17 ms 34724 KB Output is correct
3 Correct 17 ms 34764 KB Output is correct
4 Correct 19 ms 34760 KB Output is correct
5 Correct 19 ms 34744 KB Output is correct
6 Correct 18 ms 34704 KB Output is correct
7 Correct 17 ms 34640 KB Output is correct
8 Correct 17 ms 34656 KB Output is correct
9 Correct 326 ms 72428 KB Output is correct
10 Correct 34 ms 38632 KB Output is correct
11 Correct 134 ms 55120 KB Output is correct
12 Correct 44 ms 40472 KB Output is correct
13 Correct 54 ms 41352 KB Output is correct
14 Correct 18 ms 34892 KB Output is correct
15 Correct 18 ms 34892 KB Output is correct
16 Correct 355 ms 71212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 34636 KB Output is correct
2 Correct 17 ms 34724 KB Output is correct
3 Correct 17 ms 34764 KB Output is correct
4 Correct 19 ms 34760 KB Output is correct
5 Correct 19 ms 34744 KB Output is correct
6 Correct 18 ms 34704 KB Output is correct
7 Correct 17 ms 34640 KB Output is correct
8 Correct 17 ms 34656 KB Output is correct
9 Correct 326 ms 72428 KB Output is correct
10 Correct 34 ms 38632 KB Output is correct
11 Correct 134 ms 55120 KB Output is correct
12 Correct 44 ms 40472 KB Output is correct
13 Correct 54 ms 41352 KB Output is correct
14 Correct 18 ms 34892 KB Output is correct
15 Correct 18 ms 34892 KB Output is correct
16 Correct 355 ms 71212 KB Output is correct
17 Correct 16 ms 34652 KB Output is correct
18 Correct 17 ms 34752 KB Output is correct
19 Correct 16 ms 34764 KB Output is correct
20 Correct 18 ms 34644 KB Output is correct
21 Correct 18 ms 34736 KB Output is correct
22 Correct 17 ms 34764 KB Output is correct
23 Correct 991 ms 116824 KB Output is correct
24 Correct 19 ms 34764 KB Output is correct
25 Correct 19 ms 35272 KB Output is correct
26 Correct 19 ms 35152 KB Output is correct
27 Correct 19 ms 35316 KB Output is correct
28 Correct 323 ms 67956 KB Output is correct
29 Correct 532 ms 83016 KB Output is correct
30 Correct 797 ms 100764 KB Output is correct
31 Correct 1073 ms 116444 KB Output is correct
32 Correct 17 ms 34764 KB Output is correct
33 Correct 17 ms 34636 KB Output is correct
34 Correct 20 ms 34712 KB Output is correct
35 Correct 20 ms 34732 KB Output is correct
36 Correct 17 ms 34656 KB Output is correct
37 Correct 17 ms 34652 KB Output is correct
38 Correct 17 ms 34688 KB Output is correct
39 Correct 17 ms 34764 KB Output is correct
40 Correct 17 ms 34748 KB Output is correct
41 Correct 16 ms 34636 KB Output is correct
42 Correct 17 ms 34636 KB Output is correct
43 Correct 18 ms 35020 KB Output is correct
44 Correct 19 ms 35172 KB Output is correct
45 Correct 338 ms 71556 KB Output is correct
46 Correct 558 ms 89256 KB Output is correct
47 Correct 554 ms 89176 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 34636 KB Output is correct
2 Correct 17 ms 34724 KB Output is correct
3 Correct 17 ms 34764 KB Output is correct
4 Correct 19 ms 34760 KB Output is correct
5 Correct 19 ms 34744 KB Output is correct
6 Correct 18 ms 34704 KB Output is correct
7 Correct 17 ms 34640 KB Output is correct
8 Correct 17 ms 34656 KB Output is correct
9 Correct 326 ms 72428 KB Output is correct
10 Correct 34 ms 38632 KB Output is correct
11 Correct 134 ms 55120 KB Output is correct
12 Correct 44 ms 40472 KB Output is correct
13 Correct 54 ms 41352 KB Output is correct
14 Correct 18 ms 34892 KB Output is correct
15 Correct 18 ms 34892 KB Output is correct
16 Correct 355 ms 71212 KB Output is correct
17 Correct 16 ms 34652 KB Output is correct
18 Correct 17 ms 34752 KB Output is correct
19 Correct 16 ms 34764 KB Output is correct
20 Correct 18 ms 34644 KB Output is correct
21 Correct 18 ms 34736 KB Output is correct
22 Correct 17 ms 34764 KB Output is correct
23 Correct 991 ms 116824 KB Output is correct
24 Correct 19 ms 34764 KB Output is correct
25 Correct 19 ms 35272 KB Output is correct
26 Correct 19 ms 35152 KB Output is correct
27 Correct 19 ms 35316 KB Output is correct
28 Correct 323 ms 67956 KB Output is correct
29 Correct 532 ms 83016 KB Output is correct
30 Correct 797 ms 100764 KB Output is correct
31 Correct 1073 ms 116444 KB Output is correct
32 Correct 17 ms 34764 KB Output is correct
33 Correct 17 ms 34636 KB Output is correct
34 Correct 20 ms 34712 KB Output is correct
35 Correct 20 ms 34732 KB Output is correct
36 Correct 17 ms 34656 KB Output is correct
37 Correct 17 ms 34652 KB Output is correct
38 Correct 17 ms 34688 KB Output is correct
39 Correct 17 ms 34764 KB Output is correct
40 Correct 17 ms 34748 KB Output is correct
41 Correct 16 ms 34636 KB Output is correct
42 Correct 17 ms 34636 KB Output is correct
43 Correct 18 ms 35020 KB Output is correct
44 Correct 19 ms 35172 KB Output is correct
45 Correct 338 ms 71556 KB Output is correct
46 Correct 558 ms 89256 KB Output is correct
47 Correct 554 ms 89176 KB Output is correct
48 Correct 17 ms 34764 KB Output is correct
49 Correct 19 ms 34672 KB Output is correct
50 Correct 17 ms 34760 KB Output is correct
51 Correct 17 ms 34636 KB Output is correct
52 Correct 18 ms 34688 KB Output is correct
53 Correct 17 ms 34636 KB Output is correct
54 Correct 17 ms 34732 KB Output is correct
55 Incorrect 1090 ms 117380 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 16 ms 34636 KB Output is correct
2 Correct 17 ms 34724 KB Output is correct
3 Correct 17 ms 34764 KB Output is correct
4 Correct 19 ms 34760 KB Output is correct
5 Correct 19 ms 34744 KB Output is correct
6 Correct 18 ms 34704 KB Output is correct
7 Correct 17 ms 34640 KB Output is correct
8 Correct 17 ms 34656 KB Output is correct
9 Correct 326 ms 72428 KB Output is correct
10 Correct 34 ms 38632 KB Output is correct
11 Correct 134 ms 55120 KB Output is correct
12 Correct 44 ms 40472 KB Output is correct
13 Correct 54 ms 41352 KB Output is correct
14 Correct 18 ms 34892 KB Output is correct
15 Correct 18 ms 34892 KB Output is correct
16 Correct 355 ms 71212 KB Output is correct
17 Correct 17 ms 34684 KB Output is correct
18 Correct 17 ms 34692 KB Output is correct
19 Correct 16 ms 34636 KB Output is correct
20 Correct 844 ms 111788 KB Output is correct
21 Correct 858 ms 110244 KB Output is correct
22 Correct 836 ms 109676 KB Output is correct
23 Correct 654 ms 98540 KB Output is correct
24 Correct 365 ms 51976 KB Output is correct
25 Correct 491 ms 60556 KB Output is correct
26 Correct 386 ms 60528 KB Output is correct
27 Correct 878 ms 104824 KB Output is correct
28 Correct 790 ms 104640 KB Output is correct
29 Correct 1096 ms 104628 KB Output is correct
30 Correct 941 ms 104784 KB Output is correct
31 Correct 17 ms 34680 KB Output is correct
32 Correct 48 ms 40004 KB Output is correct
33 Correct 115 ms 43344 KB Output is correct
34 Correct 772 ms 110736 KB Output is correct
35 Correct 26 ms 36044 KB Output is correct
36 Correct 74 ms 41084 KB Output is correct
37 Correct 200 ms 47676 KB Output is correct
38 Correct 305 ms 63432 KB Output is correct
39 Correct 475 ms 73448 KB Output is correct
40 Correct 637 ms 85160 KB Output is correct
41 Correct 711 ms 95448 KB Output is correct
42 Correct 911 ms 105572 KB Output is correct
43 Correct 17 ms 34764 KB Output is correct
44 Correct 17 ms 34764 KB Output is correct
45 Correct 17 ms 34644 KB Output is correct
46 Correct 17 ms 34648 KB Output is correct
47 Correct 17 ms 34764 KB Output is correct
48 Correct 17 ms 34744 KB Output is correct
49 Correct 17 ms 34764 KB Output is correct
50 Correct 17 ms 34764 KB Output is correct
51 Correct 17 ms 34764 KB Output is correct
52 Correct 17 ms 34656 KB Output is correct
53 Correct 18 ms 34752 KB Output is correct
54 Correct 19 ms 35020 KB Output is correct
55 Correct 19 ms 35092 KB Output is correct
56 Correct 360 ms 71596 KB Output is correct
57 Correct 576 ms 89220 KB Output is correct
58 Correct 561 ms 89008 KB Output is correct
59 Correct 17 ms 34636 KB Output is correct
60 Correct 17 ms 34640 KB Output is correct
61 Correct 17 ms 34748 KB Output is correct
62 Correct 820 ms 109276 KB Output is correct
63 Correct 808 ms 109288 KB Output is correct
64 Correct 890 ms 109552 KB Output is correct
65 Correct 20 ms 35268 KB Output is correct
66 Correct 28 ms 35736 KB Output is correct
67 Correct 346 ms 70564 KB Output is correct
68 Correct 614 ms 90344 KB Output is correct
69 Correct 942 ms 106812 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 34636 KB Output is correct
2 Correct 17 ms 34724 KB Output is correct
3 Correct 17 ms 34764 KB Output is correct
4 Correct 19 ms 34760 KB Output is correct
5 Correct 19 ms 34744 KB Output is correct
6 Correct 18 ms 34704 KB Output is correct
7 Correct 17 ms 34640 KB Output is correct
8 Correct 17 ms 34656 KB Output is correct
9 Correct 326 ms 72428 KB Output is correct
10 Correct 34 ms 38632 KB Output is correct
11 Correct 134 ms 55120 KB Output is correct
12 Correct 44 ms 40472 KB Output is correct
13 Correct 54 ms 41352 KB Output is correct
14 Correct 18 ms 34892 KB Output is correct
15 Correct 18 ms 34892 KB Output is correct
16 Correct 355 ms 71212 KB Output is correct
17 Correct 869 ms 111336 KB Output is correct
18 Correct 875 ms 110852 KB Output is correct
19 Correct 904 ms 111768 KB Output is correct
20 Correct 992 ms 116240 KB Output is correct
21 Correct 831 ms 101228 KB Output is correct
22 Correct 17 ms 34636 KB Output is correct
23 Correct 99 ms 46568 KB Output is correct
24 Correct 41 ms 37372 KB Output is correct
25 Correct 149 ms 44516 KB Output is correct
26 Correct 265 ms 51896 KB Output is correct
27 Correct 407 ms 74360 KB Output is correct
28 Correct 561 ms 84204 KB Output is correct
29 Correct 731 ms 95120 KB Output is correct
30 Correct 878 ms 104540 KB Output is correct
31 Correct 1037 ms 114508 KB Output is correct
32 Execution timed out 3555 ms 107144 KB Time limit exceeded
33 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 34636 KB Output is correct
2 Correct 17 ms 34724 KB Output is correct
3 Correct 17 ms 34764 KB Output is correct
4 Correct 19 ms 34760 KB Output is correct
5 Correct 19 ms 34744 KB Output is correct
6 Correct 18 ms 34704 KB Output is correct
7 Correct 17 ms 34640 KB Output is correct
8 Correct 17 ms 34656 KB Output is correct
9 Correct 326 ms 72428 KB Output is correct
10 Correct 34 ms 38632 KB Output is correct
11 Correct 134 ms 55120 KB Output is correct
12 Correct 44 ms 40472 KB Output is correct
13 Correct 54 ms 41352 KB Output is correct
14 Correct 18 ms 34892 KB Output is correct
15 Correct 18 ms 34892 KB Output is correct
16 Correct 355 ms 71212 KB Output is correct
17 Correct 16 ms 34652 KB Output is correct
18 Correct 17 ms 34752 KB Output is correct
19 Correct 16 ms 34764 KB Output is correct
20 Correct 18 ms 34644 KB Output is correct
21 Correct 18 ms 34736 KB Output is correct
22 Correct 17 ms 34764 KB Output is correct
23 Correct 991 ms 116824 KB Output is correct
24 Correct 19 ms 34764 KB Output is correct
25 Correct 19 ms 35272 KB Output is correct
26 Correct 19 ms 35152 KB Output is correct
27 Correct 19 ms 35316 KB Output is correct
28 Correct 323 ms 67956 KB Output is correct
29 Correct 532 ms 83016 KB Output is correct
30 Correct 797 ms 100764 KB Output is correct
31 Correct 1073 ms 116444 KB Output is correct
32 Correct 17 ms 34764 KB Output is correct
33 Correct 17 ms 34636 KB Output is correct
34 Correct 20 ms 34712 KB Output is correct
35 Correct 20 ms 34732 KB Output is correct
36 Correct 17 ms 34656 KB Output is correct
37 Correct 17 ms 34652 KB Output is correct
38 Correct 17 ms 34688 KB Output is correct
39 Correct 17 ms 34764 KB Output is correct
40 Correct 17 ms 34748 KB Output is correct
41 Correct 16 ms 34636 KB Output is correct
42 Correct 17 ms 34636 KB Output is correct
43 Correct 18 ms 35020 KB Output is correct
44 Correct 19 ms 35172 KB Output is correct
45 Correct 338 ms 71556 KB Output is correct
46 Correct 558 ms 89256 KB Output is correct
47 Correct 554 ms 89176 KB Output is correct
48 Correct 17 ms 34764 KB Output is correct
49 Correct 19 ms 34672 KB Output is correct
50 Correct 17 ms 34760 KB Output is correct
51 Correct 17 ms 34636 KB Output is correct
52 Correct 18 ms 34688 KB Output is correct
53 Correct 17 ms 34636 KB Output is correct
54 Correct 17 ms 34732 KB Output is correct
55 Incorrect 1090 ms 117380 KB Given structure is not connected: There is no path between vertices 0 and 55
56 Halted 0 ms 0 KB -