Cod sursa(job #3333143)

Utilizator PatrikKev75Szucs Patrik - Kevin PatrikKev75 Data 11 ianuarie 2026 13:29:16
Problema Parantezare optima de matrici Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.13 kb
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

#define st first
#define nd second

struct edge
{
    int x, y;
    double w;

    bool operator<(const edge &a) const
    {
        return w < a.w;
    }
};

struct dsu
{
    vector<pair<int, int>> set;

    dsu(int n) // konstruktor
    {
        set.resize(n);
        for (int i = 0; i < n; i++)
        {
            set[i].nd = i; // parent
            set[i].st = 0; // rank
        }
    }

    int find(int x)
    {
        if (set[x].nd != x)
            set[x].nd = find(set[x].nd);

        return set[x].nd;
    }

    bool unite(int x, int y)
    {
        x = find(x);
        y = find(y);

        if (x == y)
            return false;

        if (set[x].st < set[y].st)
            swap(x, y);

        set[y].nd = x;
        if (set[x].st == set[y].st)
            set[x].st++;

        return true;
    }
};

void merge(vector<edge> &a, vector<edge> &b)
{
    int i = 0, j = 0, n = 0;
    vector<edge> tmp(a.size() + b.size()); // n lesz az indexe

    while (i <= a.size() && j <= b.size())
    {
        if (a[i])
    }
}

int main()
{
    int n;

    ifstream in("desen.in");
    ofstream out("desen.out");
    in >> n;

    vector<edge> prev;
    vector<pair<int, int>> p(n);
    for (int i = 0; i < n; i++)
    {
        vector<edge> edges;
        edges.reserve(2 * i);
        in >> p[i].first >> p[i].second;

        for (int j = 0; j < i; j++)
        {
            double dx = p[i].first - p[j].first;
            double dy = p[i].second - p[j].second;
            edges.push_back({i, j, sqrt(dx * dx + dy * dy)});
        }

        sort(edges.begin(), edges.end());

        dsu set(i + 1);
        double s = 0;
        vector<edge> idk;
        idk.reserve(i);

        for (auto &e : edges)
        {
            if ((int)idk.size() == i)
                break;

            if (set.unite(e.x, e.y))
            {
                s += e.w;
                idk.push_back(e);
            }
        }

        prev = idk;
        out << fixed << setprecision(6) << s << '\n';
    }
    in.close();
    out.close();

    return 0;
}