oj.uz

Submission #865433

# Submission time Handle Problem Language Result Execution time Memory
865433 2023-10-24T08:21:34 Z boris_mihov Roads (CEOI20_roads) C++17
0 / 100
 266 ms 19740 KB 
#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];
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 <= 20 ; ++j)
        {
            int curr = rng() % (2 * n) + 1;
            if (abs(i - curr) % n == 0) continue;
            mst.push_back({i, curr});
        }
    } 

    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 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2516 KB Output is correct
2 Failed 266 ms 19740 KB Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])"
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Failed 2 ms 2396 KB Condition failed: "pf == Sline.end() || !Cross(S[*pa], S[*pf])"
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Failed 2 ms 2396 KB Condition failed: "pf == Sline.end() || !Cross(S[*pa], S[*pf])"
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Failed 2 ms 2524 KB Condition failed: "pf == Sline.end() || !Cross(S[*pa], S[*pf])"
3 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Failed 1 ms 2524 KB Condition failed: "pf == Sline.end() || !Cross(S[*pa], S[*pf])"
4 Halted 0 ms 0 KB -

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Failed 263 ms 19408 KB Condition failed: "pf == Sline.end() || !Cross(S[*pi], S[*pf])"
3 Halted 0 ms 0 KB -