oj.uz

Submission #446954

# Submission time Handle Problem Language Result Execution time Memory
446954 2021-07-24T05:04:14 Z blue Fountain Parks (IOI21_parks) C++17
35 / 100
 3500 ms 117420 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 == 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 20 ms 34720 KB Output is correct
2 Correct 17 ms 34724 KB Output is correct
3 Correct 17 ms 34680 KB Output is correct
4 Correct 17 ms 34744 KB Output is correct
5 Correct 17 ms 34652 KB Output is correct
6 Correct 18 ms 34764 KB Output is correct
7 Correct 17 ms 34644 KB Output is correct
8 Correct 19 ms 34764 KB Output is correct
9 Correct 307 ms 72548 KB Output is correct
10 Correct 34 ms 38596 KB Output is correct
11 Correct 128 ms 55112 KB Output is correct
12 Correct 48 ms 40404 KB Output is correct
13 Correct 52 ms 41340 KB Output is correct
14 Correct 17 ms 34872 KB Output is correct
15 Correct 18 ms 34988 KB Output is correct
16 Correct 305 ms 71200 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 34720 KB Output is correct
2 Correct 17 ms 34724 KB Output is correct
3 Correct 17 ms 34680 KB Output is correct
4 Correct 17 ms 34744 KB Output is correct
5 Correct 17 ms 34652 KB Output is correct
6 Correct 18 ms 34764 KB Output is correct
7 Correct 17 ms 34644 KB Output is correct
8 Correct 19 ms 34764 KB Output is correct
9 Correct 307 ms 72548 KB Output is correct
10 Correct 34 ms 38596 KB Output is correct
11 Correct 128 ms 55112 KB Output is correct
12 Correct 48 ms 40404 KB Output is correct
13 Correct 52 ms 41340 KB Output is correct
14 Correct 17 ms 34872 KB Output is correct
15 Correct 18 ms 34988 KB Output is correct
16 Correct 305 ms 71200 KB Output is correct
17 Correct 17 ms 34720 KB Output is correct
18 Correct 16 ms 34692 KB Output is correct
19 Correct 18 ms 34724 KB Output is correct
20 Correct 17 ms 34644 KB Output is correct
21 Correct 18 ms 34644 KB Output is correct
22 Correct 17 ms 34716 KB Output is correct
23 Correct 1006 ms 116768 KB Output is correct
24 Correct 17 ms 34636 KB Output is correct
25 Correct 21 ms 35188 KB Output is correct
26 Correct 19 ms 35148 KB Output is correct
27 Correct 21 ms 35316 KB Output is correct
28 Correct 299 ms 67812 KB Output is correct
29 Correct 524 ms 83160 KB Output is correct
30 Correct 830 ms 100868 KB Output is correct
31 Correct 1059 ms 116316 KB Output is correct
32 Correct 17 ms 34764 KB Output is correct
33 Correct 17 ms 34764 KB Output is correct
34 Correct 19 ms 34704 KB Output is correct
35 Correct 19 ms 34668 KB Output is correct
36 Correct 17 ms 34644 KB Output is correct
37 Correct 17 ms 34764 KB Output is correct
38 Correct 19 ms 34724 KB Output is correct
39 Correct 17 ms 34748 KB Output is correct
40 Correct 17 ms 34748 KB Output is correct
41 Correct 17 ms 34756 KB Output is correct
42 Correct 17 ms 34644 KB Output is correct
43 Correct 19 ms 35020 KB Output is correct
44 Correct 19 ms 35116 KB Output is correct
45 Correct 352 ms 71668 KB Output is correct
46 Correct 600 ms 89336 KB Output is correct
47 Correct 536 ms 89084 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 34720 KB Output is correct
2 Correct 17 ms 34724 KB Output is correct
3 Correct 17 ms 34680 KB Output is correct
4 Correct 17 ms 34744 KB Output is correct
5 Correct 17 ms 34652 KB Output is correct
6 Correct 18 ms 34764 KB Output is correct
7 Correct 17 ms 34644 KB Output is correct
8 Correct 19 ms 34764 KB Output is correct
9 Correct 307 ms 72548 KB Output is correct
10 Correct 34 ms 38596 KB Output is correct
11 Correct 128 ms 55112 KB Output is correct
12 Correct 48 ms 40404 KB Output is correct
13 Correct 52 ms 41340 KB Output is correct
14 Correct 17 ms 34872 KB Output is correct
15 Correct 18 ms 34988 KB Output is correct
16 Correct 305 ms 71200 KB Output is correct
17 Correct 17 ms 34720 KB Output is correct
18 Correct 16 ms 34692 KB Output is correct
19 Correct 18 ms 34724 KB Output is correct
20 Correct 17 ms 34644 KB Output is correct
21 Correct 18 ms 34644 KB Output is correct
22 Correct 17 ms 34716 KB Output is correct
23 Correct 1006 ms 116768 KB Output is correct
24 Correct 17 ms 34636 KB Output is correct
25 Correct 21 ms 35188 KB Output is correct
26 Correct 19 ms 35148 KB Output is correct
27 Correct 21 ms 35316 KB Output is correct
28 Correct 299 ms 67812 KB Output is correct
29 Correct 524 ms 83160 KB Output is correct
30 Correct 830 ms 100868 KB Output is correct
31 Correct 1059 ms 116316 KB Output is correct
32 Correct 17 ms 34764 KB Output is correct
33 Correct 17 ms 34764 KB Output is correct
34 Correct 19 ms 34704 KB Output is correct
35 Correct 19 ms 34668 KB Output is correct
36 Correct 17 ms 34644 KB Output is correct
37 Correct 17 ms 34764 KB Output is correct
38 Correct 19 ms 34724 KB Output is correct
39 Correct 17 ms 34748 KB Output is correct
40 Correct 17 ms 34748 KB Output is correct
41 Correct 17 ms 34756 KB Output is correct
42 Correct 17 ms 34644 KB Output is correct
43 Correct 19 ms 35020 KB Output is correct
44 Correct 19 ms 35116 KB Output is correct
45 Correct 352 ms 71668 KB Output is correct
46 Correct 600 ms 89336 KB Output is correct
47 Correct 536 ms 89084 KB Output is correct
48 Correct 18 ms 34648 KB Output is correct
49 Correct 17 ms 34676 KB Output is correct
50 Correct 17 ms 34720 KB Output is correct
51 Correct 17 ms 34708 KB Output is correct
52 Correct 18 ms 34684 KB Output is correct
53 Correct 17 ms 34616 KB Output is correct
54 Correct 17 ms 34672 KB Output is correct
55 Incorrect 1103 ms 117420 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 20 ms 34720 KB Output is correct
2 Correct 17 ms 34724 KB Output is correct
3 Correct 17 ms 34680 KB Output is correct
4 Correct 17 ms 34744 KB Output is correct
5 Correct 17 ms 34652 KB Output is correct
6 Correct 18 ms 34764 KB Output is correct
7 Correct 17 ms 34644 KB Output is correct
8 Correct 19 ms 34764 KB Output is correct
9 Correct 307 ms 72548 KB Output is correct
10 Correct 34 ms 38596 KB Output is correct
11 Correct 128 ms 55112 KB Output is correct
12 Correct 48 ms 40404 KB Output is correct
13 Correct 52 ms 41340 KB Output is correct
14 Correct 17 ms 34872 KB Output is correct
15 Correct 18 ms 34988 KB Output is correct
16 Correct 305 ms 71200 KB Output is correct
17 Correct 17 ms 34700 KB Output is correct
18 Correct 17 ms 34764 KB Output is correct
19 Correct 17 ms 34696 KB Output is correct
20 Correct 836 ms 111872 KB Output is correct
21 Correct 819 ms 110304 KB Output is correct
22 Correct 834 ms 109560 KB Output is correct
23 Correct 678 ms 98388 KB Output is correct
24 Correct 276 ms 51884 KB Output is correct
25 Correct 412 ms 60560 KB Output is correct
26 Correct 399 ms 60552 KB Output is correct
27 Correct 793 ms 104848 KB Output is correct
28 Correct 881 ms 104724 KB Output is correct
29 Correct 971 ms 104724 KB Output is correct
30 Correct 891 ms 104748 KB Output is correct
31 Correct 17 ms 34684 KB Output is correct
32 Correct 54 ms 39892 KB Output is correct
33 Correct 115 ms 43420 KB Output is correct
34 Correct 749 ms 110836 KB Output is correct
35 Correct 26 ms 36044 KB Output is correct
36 Correct 81 ms 41108 KB Output is correct
37 Correct 201 ms 47620 KB Output is correct
38 Correct 244 ms 63380 KB Output is correct
39 Correct 364 ms 73492 KB Output is correct
40 Correct 595 ms 85164 KB Output is correct
41 Correct 695 ms 95396 KB Output is correct
42 Correct 892 ms 105696 KB Output is correct
43 Correct 17 ms 34636 KB Output is correct
44 Correct 20 ms 34768 KB Output is correct
45 Correct 17 ms 34668 KB Output is correct
46 Correct 19 ms 34676 KB Output is correct
47 Correct 17 ms 34640 KB Output is correct
48 Correct 17 ms 34684 KB Output is correct
49 Correct 17 ms 34764 KB Output is correct
50 Correct 17 ms 34656 KB Output is correct
51 Correct 19 ms 34636 KB Output is correct
52 Correct 17 ms 34748 KB Output is correct
53 Correct 17 ms 34740 KB Output is correct
54 Correct 18 ms 35020 KB Output is correct
55 Correct 19 ms 35156 KB Output is correct
56 Correct 351 ms 71548 KB Output is correct
57 Correct 533 ms 89220 KB Output is correct
58 Correct 577 ms 89036 KB Output is correct
59 Correct 17 ms 34704 KB Output is correct
60 Correct 18 ms 34724 KB Output is correct
61 Correct 17 ms 34636 KB Output is correct
62 Correct 815 ms 109256 KB Output is correct
63 Correct 786 ms 109248 KB Output is correct
64 Correct 811 ms 109544 KB Output is correct
65 Correct 20 ms 35276 KB Output is correct
66 Correct 26 ms 35788 KB Output is correct
67 Correct 323 ms 70504 KB Output is correct
68 Correct 563 ms 90316 KB Output is correct
69 Correct 882 ms 106960 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 34720 KB Output is correct
2 Correct 17 ms 34724 KB Output is correct
3 Correct 17 ms 34680 KB Output is correct
4 Correct 17 ms 34744 KB Output is correct
5 Correct 17 ms 34652 KB Output is correct
6 Correct 18 ms 34764 KB Output is correct
7 Correct 17 ms 34644 KB Output is correct
8 Correct 19 ms 34764 KB Output is correct
9 Correct 307 ms 72548 KB Output is correct
10 Correct 34 ms 38596 KB Output is correct
11 Correct 128 ms 55112 KB Output is correct
12 Correct 48 ms 40404 KB Output is correct
13 Correct 52 ms 41340 KB Output is correct
14 Correct 17 ms 34872 KB Output is correct
15 Correct 18 ms 34988 KB Output is correct
16 Correct 305 ms 71200 KB Output is correct
17 Correct 819 ms 111372 KB Output is correct
18 Correct 786 ms 110840 KB Output is correct
19 Correct 888 ms 111700 KB Output is correct
20 Correct 1037 ms 116276 KB Output is correct
21 Correct 875 ms 101160 KB Output is correct
22 Correct 17 ms 34636 KB Output is correct
23 Correct 100 ms 46532 KB Output is correct
24 Correct 37 ms 37364 KB Output is correct
25 Correct 109 ms 44304 KB Output is correct
26 Correct 229 ms 51884 KB Output is correct
27 Correct 413 ms 74344 KB Output is correct
28 Correct 526 ms 84188 KB Output is correct
29 Correct 685 ms 95120 KB Output is correct
30 Correct 844 ms 104452 KB Output is correct
31 Correct 1030 ms 114428 KB Output is correct
32 Execution timed out 3569 ms 106972 KB Time limit exceeded
33 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 34720 KB Output is correct
2 Correct 17 ms 34724 KB Output is correct
3 Correct 17 ms 34680 KB Output is correct
4 Correct 17 ms 34744 KB Output is correct
5 Correct 17 ms 34652 KB Output is correct
6 Correct 18 ms 34764 KB Output is correct
7 Correct 17 ms 34644 KB Output is correct
8 Correct 19 ms 34764 KB Output is correct
9 Correct 307 ms 72548 KB Output is correct
10 Correct 34 ms 38596 KB Output is correct
11 Correct 128 ms 55112 KB Output is correct
12 Correct 48 ms 40404 KB Output is correct
13 Correct 52 ms 41340 KB Output is correct
14 Correct 17 ms 34872 KB Output is correct
15 Correct 18 ms 34988 KB Output is correct
16 Correct 305 ms 71200 KB Output is correct
17 Correct 17 ms 34720 KB Output is correct
18 Correct 16 ms 34692 KB Output is correct
19 Correct 18 ms 34724 KB Output is correct
20 Correct 17 ms 34644 KB Output is correct
21 Correct 18 ms 34644 KB Output is correct
22 Correct 17 ms 34716 KB Output is correct
23 Correct 1006 ms 116768 KB Output is correct
24 Correct 17 ms 34636 KB Output is correct
25 Correct 21 ms 35188 KB Output is correct
26 Correct 19 ms 35148 KB Output is correct
27 Correct 21 ms 35316 KB Output is correct
28 Correct 299 ms 67812 KB Output is correct
29 Correct 524 ms 83160 KB Output is correct
30 Correct 830 ms 100868 KB Output is correct
31 Correct 1059 ms 116316 KB Output is correct
32 Correct 17 ms 34764 KB Output is correct
33 Correct 17 ms 34764 KB Output is correct
34 Correct 19 ms 34704 KB Output is correct
35 Correct 19 ms 34668 KB Output is correct
36 Correct 17 ms 34644 KB Output is correct
37 Correct 17 ms 34764 KB Output is correct
38 Correct 19 ms 34724 KB Output is correct
39 Correct 17 ms 34748 KB Output is correct
40 Correct 17 ms 34748 KB Output is correct
41 Correct 17 ms 34756 KB Output is correct
42 Correct 17 ms 34644 KB Output is correct
43 Correct 19 ms 35020 KB Output is correct
44 Correct 19 ms 35116 KB Output is correct
45 Correct 352 ms 71668 KB Output is correct
46 Correct 600 ms 89336 KB Output is correct
47 Correct 536 ms 89084 KB Output is correct
48 Correct 18 ms 34648 KB Output is correct
49 Correct 17 ms 34676 KB Output is correct
50 Correct 17 ms 34720 KB Output is correct
51 Correct 17 ms 34708 KB Output is correct
52 Correct 18 ms 34684 KB Output is correct
53 Correct 17 ms 34616 KB Output is correct
54 Correct 17 ms 34672 KB Output is correct
55 Incorrect 1103 ms 117420 KB Given structure is not connected: There is no path between vertices 0 and 110
56 Halted 0 ms 0 KB -