Submission #1065084

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065084		ThegeekKnight16	Roads (CEOI20_roads)	C++17	0 / 100	545 ms	524288 KiB

roads

#include <bits/stdc++.h>
using namespace std;
struct ponto
{
    long long x, y;

    ponto(long long X = 0, long long Y = 0) : x(X), y(Y) {}

    ponto operator+ (ponto outro) const {return ponto(x + outro.x, y + outro.x);}
    ponto operator- (ponto outro) const {return ponto(x - outro.x, y - outro.y);}
    long long operator* (ponto outro) const {return (x * outro.x) + (y*outro.y);}
    long long operator^ (ponto outro) const {return (x * outro.y) - (y*outro.x);}

    bool operator< (ponto outro) const {return (x == outro.x ? y < outro.y : x < outro.x);}
};
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// mt19937 rng(69);
vector<int> pai, sub;

int find(int v) {return pai[v] = (pai[v] == v ? v : find(pai[v]));}
void une(int x, int y, vector<pair<int, int>> &resp)
{
    int px = find(x), py = find(y);
    if (px == py) return;
    if (sub[px] < sub[py]) swap(px, py);
    resp.emplace_back(x, y);
    pai[py] = px; sub[px] += sub[py];
}

void dc(vector<pair<int, int>> &activeE, vector<int> &activeP, vector<pair<int, int>> &resp, const vector<ponto> &v)
{
    if (activeE.empty())
    {
        if (activeP.empty()) return;
        sort(activeP.begin(), activeP.end(), [&](const int &a, const int &b) {return v[a] < v[b];});
        for (int i = 0; i < activeP.size()-1; i++) une(activeP[i], activeP[i+1], resp);
        activeP.clear();
        return;
    }

    int idE = uniform_int_distribution<int>(0, (int)activeE.size()-1)(rng);
    auto [l, r] = activeE[idE];
    if (v[r] < v[l]) swap(l, r);
    vector<pair<int, int>> lE, rE;
    vector<int> lP(1, l), rP(1, r);

    for (auto p : activeP)
    {
        long long dir = ((v[r]-v[l])^(v[p]-v[l]));
        if (dir == 0) dir = ((v[p] < v[l]) ? -1 : 1);
        if (dir < 0LL) lP.push_back(p);
        else rP.push_back(p);
    }

    for (auto [L, R] : activeE)
    {
        if (L == l && R == r) continue;
        long long dirL = ((v[r]-v[l])^(v[L]-v[l]));
        if (dirL == 0) dirL = ((v[L] < v[l]) ? -1 : 1);
        else dirL = (dirL < 0 ? -1 : 1);
        long long dirR = ((v[r]-v[l])^(v[R]-v[l]));
        if (dirR == 0) dirR = ((v[R] < v[l]) ? -1 : 1);
        else dirR = (dirR < 0 ? -1 : 1);
        if (dirL * dirR > 0LL) //Dois p/ mesmo lado
        {
            if (dirL < 0LL) lE.emplace_back(L, R);
            else rE.emplace_back(L, R);
        }
        else
        {
            if (dirL < 0LL) lP.push_back(L), rP.push_back(R);
            else lP.push_back(R), rP.push_back(L);
        }
    }
    activeE.clear(); activeP.clear();

    dc(lE, lP, resp, v);
    dc(rE, rP, resp, v);
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    cin >> N;
    vector<ponto> v(2*N);
    pai.resize(2*N); iota(pai.begin(), pai.end(), 0);
    sub.resize(2*N); fill(sub.begin(), sub.end(), 1);
    for (int i = 0; i < 2*N; i++) cin >> v[i].x >> v[i].y;
    vector<pair<int, int>> resp;
    vector<pair<int, int>> activeE; vector<int> activeP;
    for (int i = 0; i < 2*N; i+=2) une(i, i+1, activeE);
    dc(activeE, activeP, resp, v);

    for (auto &[i, j] : resp) cout << v[i].x << " " << v[i].y << " " << v[j].x << " " << v[j].y << '\n';
}

Compilation message (stderr)

roads.cpp: In function 'void dc(std::vector<std::pair<int, int> >&, std::vector<int>&, std::vector<std::pair<int, int> >&, const std::vector<ponto>&)':
roads.cpp:36:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for (int i = 0; i < activeP.size()-1; i++) une(activeP[i], activeP[i+1], resp);
      |                         ~~^~~~~~~~~~~~~~~~~~

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