Submission #865462

#	Time	Username	Problem	Language	Result	Execution time	Memory
865462		boris_mihov	Roads (CEOI20_roads)	C++17	0 / 100	1090 ms	5960 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 (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

Point p[MAXN];
int idx[MAXN];

struct MstElement
{
    int x, y;
    friend bool operator < (const MstElement &a, const MstElement &b)
    {
        return dist(p[a.x], p[a.y]) > dist(p[b.x], p[b.y]);
    }
};

std::priority_queue <MstElement> mst;
void pushMIN(int x, int y)
{
    llong distA = dist(p[x], p[y]);
    llong distB = dist(p[x], p[n + y]);
    llong distC = dist(p[n + x], p[y]);
    llong distD = dist(p[n + x], p[n + y]);
    if (distA <= distB && distA <= distC && distA <= distD)
    {
        mst.push({x, y});
        return;
    }

    if (distB <= distC && distB <= distD)
    {
        mst.push({x, n + y});
        return;
    }

    if (distC <= distD)
    {
        mst.push({n + x, y});
        return;
    }

    mst.push({x + n, y + n});
}

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;
    for (int i = 1 ; i <= n ; ++i)
    {   
        for (int j = 1 ; j <= n ; ++j)
        {
            if (i == j) continue;
            if (idx[i] == 0 || dist(p[i], p[j]) < dist(p[i], p[idx[i]]))
            {
                idx[i] = j;
            }
        }
        
        pushMIN(i, idx[i]);
    } 

    while (answer.size() < n - 1)
    {
        auto [x, y] = mst.top();
        mst.pop();

        if (dsu.areConnected(x, y))
        {
            continue;
        }

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

        if (x > n) x -= n;
        if (y > n) y -= n;
        idx[x] = idx[y] = 0;
        for (int i = 1 ; i <= n ; ++i)
        {
            if (dsu.areConnected(x, i)) continue;
            if (idx[x] == 0 || dist(p[x], p[i]) < dist(p[x], p[idx[x]]))
            {
                idx[x] = i;
            }
        }

        for (int i = 1 ; i <= n ; ++i)
        {
            if (dsu.areConnected(y, i)) continue;
            if (idx[y] == 0 || dist(p[y], p[i]) < dist(p[y], p[idx[y]]))
            {
                idx[y] = i;
            }
        }   
        
        pushMIN(x, idx[x]);
        pushMIN(y, idx[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;
}

Compilation message (stderr)

roads.cpp: In function 'void solve()':
roads.cpp:134:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<Point, Point> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  134 |     while (answer.size() < n - 1)
      |            ~~~~~~~~~~~~~~^~~~~~~

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