제출 #446408

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446408		luciocf	분수 공원 (IOI21_parks)	C++17	30 / 100	1306 ms	70076 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"

using namespace std;

const int maxn = 2e5+10;

int linha[] = {-2, 2, 0, 0};
int coluna[] = {0, 0, -2, 2};

struct Pt
{
    int x, y, ind;
} a[maxn];

struct Road
{
    int u, v, x, y;
} road[maxn];

struct DSU
{
    int pai[maxn], peso[maxn];

    void init(int n)
    {
        for (int i = 1; i <= n; i++)
            pai[i] = i;
    }

    int Find(int x)
    {
        if (pai[x] == x) return x;
        return pai[x] = Find(pai[x]);
    }

    void Join(int x, int y)
    {
        x = Find(x), y = Find(y);
        if (x == y) return;

        if (peso[x] < peso[y]) swap(x, y);

        pai[y] = x, peso[x] += peso[y]; 
    }
} dsu;

bool comp(Pt a, Pt b)
{
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

int construct_roads(vector<int> X, vector<int> Y)
{
    int n = X.size();

    bool sub = 1;
    int mn = 8, mx = 0;

    map<pair<int, int>, int> mp;

    for (int i = 1; i <= n; i++)
    {
        a[i] = {X[i-1], Y[i-1], i};

        mp[{a[i].x, a[i].y}] = i;

        mx = max(mx, a[i].x);
        mn = min(mn, a[i].x);
    }

    if (mx > 6) sub = 0;

    dsu.init(n);

    if (sub)
    {
        map<pair<int, int>, int> bench;

        sort(a+1, a+n+1, comp);

        int ind = 0;

        for (int i = 1; i < n; i++)
        {
            if (dsu.Find(a[i].ind) != dsu.Find(a[i+1].ind) && a[i].x == a[i+1].x && a[i].y+2 == a[i+1].y)
            {
                dsu.Join(a[i].ind, a[i+1].ind);

                road[++ind] = {a[i].ind, a[i+1].ind, a[i].x-1, a[i].y+1};

                if (a[i].x == mx)
                {
                    road[ind].x = a[i].x+1, road[ind].y = a[i].y+1;
                    bench[{a[i].x+1, a[i].y+1}] = 1;
                }
                else if (a[i].x == mn)
                {
                    bench[{a[i].x-1, a[i].y+1}] = 1;
                } 
                else
                {
                    if (bench[{a[i].x-1, a[i].y+1}] == 1)
                    {
                        road[ind].x = a[i].x+1, road[ind].y = a[i].y+1;
                        bench[{a[i].x+1, a[i].y+1}] = 1;
                    }
                    else
                    {
                        bench[{a[i].x-1, a[i].y+1}] = 1;
                    }
                }
            }

            if (mp[{a[i].x+2, a[i].y}] && dsu.Find(a[i].ind) != dsu.Find(mp[{a[i].x+2, a[i].y}]))
            {
                dsu.Join(a[i].ind, mp[{a[i].x+2, a[i].y}]);

                if (bench[{a[i].x+1, a[i].y-1}])
                {
                    road[++ind] = {a[i].ind, mp[{a[i].x+2, a[i].y}], a[i].x+1, a[i].y+1};
                    bench[{a[i].x+1, a[i].y+1}] = 1;
                }
                else
                {
                    road[++ind] = {a[i].ind, mp[{a[i].x+2, a[i].y}], a[i].x+1, a[i].y-1};
                    bench[{a[i].x+1, a[i].y-1}] = 1;
                }
            }
        }

        if (ind != n-1) return 0;

        vector<int> U, V, A, B;

        for (int i = 1; i < n; i++)
        {
            U.push_back(road[i].u-1), V.push_back(road[i].v-1);
            A.push_back(road[i].x), B.push_back(road[i].y);
        }

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

    map<pair<int, int>, int> bench;

    int ind = 0;

    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            int dx = a[i].x+linha[j], dy = a[i].y+coluna[j];

            if (!mp[{dx, dy}]) continue;

            int o = mp[{dx, dy}];

            if (dsu.Find(i) != dsu.Find(o) && a[i].x == a[o].x && a[i].y+2 == a[o].y)
            {
                dsu.Join(i, o);

                road[++ind] = {a[i].ind, a[i+1].ind, a[i].x-1, a[i].y+1};

                if (bench[{a[i].x-1, a[i].y+1}] == 1)
                {
                    road[ind].x = a[i].x+1, road[ind].y = a[i].y+1;
                    bench[{a[i].x+1, a[i].y+1}] = 1;
                }
                else
                {
                    bench[{a[i].x-1, a[i].y+1}] = 1;
                }
            }

            if (dsu.Find(i) != dsu.Find(o) && a[i].x+2 == a[o].x)
            {
                dsu.Join(i, o);

                if (bench[{a[i].x+1, a[i].y-1}])
                {
                    road[++ind] = {a[i].ind, mp[{a[i].x+2, a[i].y}], a[i].x+1, a[i].y+1};
                    bench[{a[i].x+1, a[i].y+1}] = 1;
                }
                else
                {
                    road[++ind] = {a[i].ind, mp[{a[i].x+2, a[i].y}], a[i].x+1, a[i].y-1};
                    bench[{a[i].x+1, a[i].y-1}] = 1;
                }
            }
        }
    }

    if (ind != n-1) return 0;

    vector<int> U, V, A, B;

    for (int i = 1; i < n; i++)
    {
        U.push_back(road[i].u-1), V.push_back(road[i].v-1);
        A.push_back(road[i].x), B.push_back(road[i].y);
    }

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

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