oj.uz

Submission #865453

# Submission time Handle Problem Language Result Execution time Memory
865453 2023-10-24T08:40:40 Z boris_mihov Roads (CEOI20_roads) C++17
0 / 100
 1000 ms 6036 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 abs(a.x - b.x) + abs(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::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::priority_queue <MstElement> mst;
    for (int i = 1 ; i <= 2 * n ; ++i)
    {   
        for (int j = 1 ; j <= 1000 ; ++j)
        {
            int curr = rng() % (2 * n) + 1;
            if (abs(i - curr) % n == 0) continue;
            if (idx[i] == 0 || dist(p[i], p[curr]) < dist(p[i], p[idx[i]]))
            {
                idx[i] = curr;
            }
        }
        
        mst.push({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);

        idx[x] = idx[y] = 0;
        for (int i = 1 ; i <= 2 * 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 <= 2 * 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;
            }
        }   

        mst.push({x, idx[x]});
        mst.push({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

roads.cpp: In function 'void solve()':
roads.cpp:108: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]
  108 |     while (answer.size() < n - 1)
      |            ~~~~~~~~~~~~~~^~~~~~~

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Execution timed out 1082 ms 6036 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Execution timed out 1094 ms 6028 KB Time limit exceeded
3 Halted 0 ms 0 KB -