Submission #865441

#	Time	Username	Problem	Language	Result	Execution time	Memory
865441		boris_mihov	Roads (CEOI20_roads)	C++17	0 / 100	648 ms	524288 KiB

roads

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <random>
#include <queue>
#include <stack>
#include <set>

typedef long long llong;
const int MAXN = 200000 + 10;
const int MOD = 1e9 + 7;
const int INF = 2e9;

int n;
struct DSU
{
    int par[MAXN];
    int dep[MAXN];

    void build()
    {
        std::iota(par + 1, par + 1 + 2 * n, 1);
        std::fill(dep + 1, dep + 1 + 2 * n, 1);
    }

    int find(int node)
    {
        if (par[node] == node) return node;
        return par[node] = find(par[node]);
    }

    void connect(int u, int v)
    {
        u = find(u);
        v = find(v);
        assert(u != v);
    
        if (dep[u] > dep[v])
        {
            std::swap(u, v);
        }

        if (dep[u] == dep[v])
        {
            dep[v]++;
        }

        par[u] = v;
    }

    bool areConnected(int u, int v)
    {
        return find(u) == find(v);
    }
};

DSU dsu;
struct Point
{
    llong x, y;
};

llong dist(Point a, Point b)
{
    return abs(a.x - b.x) + abs(a.y - b.y);
}

Point p[MAXN];
std::mt19937 rng(69420);
void solve()
{
    dsu.build();
    for (int i = 1 ; i <= n ; ++i)
    {
        dsu.connect(i, n + i);
    }

    std::vector <std::pair <Point,Point>> answer;
    std::vector <std::pair <int,int>> mst;
    mst.reserve(n * n * 4);
    for (int i = 1 ; i <= 2 * n ; ++i)
    {   
        for (int j = 1 ; j <= 2 * n ; ++j)
        {
            // int curr = rng() % (2 * n) + 1;
            if (abs(i - j) % n == 0) continue;
            mst.push_back({i, j});
        }
    } 

    std::sort(mst.begin(), mst.end(), [&](auto p1, auto p2)
    {
        return dist(p[p1.first], p[p1.second]) < dist(p[p2.first], p[p2.second]);
    });

    for (const auto &[x, y] : mst)
    {
        if (dsu.areConnected(x, y))
        {
            continue;
        }

        answer.push_back({p[x], p[y]});
        dsu.connect(x, y);
    }

    // assert(answer.size() == n - 1);
    for (const auto &[p1, p2] : answer)
    {
        std::cout << p1.x << ' ' << p1.y << ' ' << p2.x << ' ' << p2.y << '\n';
    }
}   

void input()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> p[i].x >> p[i].y >> p[n + i].x >> p[n + i].y;
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 40