Submission #446948

#	Time	Username	Problem	Language	Result	Execution time	Memory
446948		blue	Fountain Parks (IOI21_parks)	C++17	25 / 100	3587 ms	131824 KiB

parks

#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;






const int X_orient = 0;
const int Y_orient = 1;

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

    int orientation()
    {
        if((x+y)%4 == 2) return X_orient;
        else return Y_orient;
    }
};

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> path_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[new_bench.i].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 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 20 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30