Submission #446965

#	Time	Username	Problem	Language	Result	Execution time	Memory
446965		blue	Fountain Parks (IOI21_parks)	C++17	100 / 100	1308 ms	73640 KiB

parks

#include "parks.h"
#include <vector>
#include <set>
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;

const int maxN = 200'000;

int N;
vector<int> X, Y;


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 obj
{
    int i;
    int x;
    int y;
};

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

set<obj> fountains;
set<obj> benches;

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

int bench_id = -1;
void insert_bench(int x, int y)
{
    set<obj>::iterator it = benches.find(obj{-1, x, y});
    if(it == benches.end())
    {
        bench_id++;
        benches.insert(obj{bench_id, x, y});
    }
}


vector<int> U, V, A, B;
void add_edge(int u, int v, int a, int b)
{
    // printf("add_edge %d(%d, %d) - %d(%d, %d) with bench at (%d, %d) \n", u, X[u], Y[u], v, X[v], Y[v], a, b);
    U.push_back(u);
    V.push_back(v);
    A.push_back(a);
    B.push_back(b);
}



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(obj{i, x[i], y[i]});



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

        I = point_index(x[i] - 2, y[i]);
        if(I != -1)
        {
            fountain_edge[i].push_back(I);
            fountain_edge[I].push_back(i);
        }

        I = point_index(x[i], y[i] - 2);
        if(I != -1)
        {
            fountain_edge[i].push_back(I);
            fountain_edge[I].push_back(i);
        }

        insert_bench(x[i] - 1, y[i] - 1);
        insert_bench(x[i] + 1, y[i] - 1);
        insert_bench(x[i] - 1, y[i] + 1);
        insert_bench(x[i] + 1, y[i] + 1);
    }



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

    for(obj B: benches)
    {
        // cerr << "B = " << B.x << ' ' << B.y << '\n';
        int P1, P2;
        if((B.x + B.y) % 4 == 0) //horizontal
        {
            // cerr << "horizontal\n";
            P1 = point_index(B.x - 1, B.y - 1);
            P2 = point_index(B.x + 1, B.y - 1);
            if(P1 != -1 && P2 != -1)
            {
                add_edge(P1, P2, B.x, B.y);
                continue;
            }



            P1 = point_index(B.x - 1, B.y + 1);
            P2 = point_index(B.x + 1, B.y + 1);
            if(P1 != -1 && P2 != -1)
                add_edge(P1, P2, B.x, B.y);
        }
        else
        {
            // cerr << "vertical\n";
            P1 = point_index(B.x - 1, B.y - 1);
            P2 = point_index(B.x - 1, B.y + 1);

            // cerr << B.x - 1 << ' ' << B.y - 1 << "    " << B.x - 1 << ' ' << B.y + 1 << '\n';
            // cerr << P1 << ' ' << P2 << '\n';

            if(P1 != -1 && P2 != -1)
            {
                add_edge(P1, P2, B.x, B.y);
                continue;
            }

            P1 = point_index(B.x + 1, B.y - 1);
            P2 = point_index(B.x + 1, B.y + 1);
            if(P1 != -1 && P2 != -1)
            {
                add_edge(P1, P2, B.x, B.y);
            }
        }
    }

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

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30