Cod sursa(job #2896988)

Utilizator vlad2009Vlad Tutunaru vlad2009 Data 1 mai 2022 21:15:59
Problema A+B Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#include <vector>

using namespace std;

struct Edge {
    int u;
    int v;
    int cost;
};

bool operator < (const Edge &a, const Edge &b) {
    return a.cost < b.cost;
}

const int MAX_N = 2 * 1e8;
int parent[MAX_N + 1], t[MAX_N + 1];
vector<Edge> edges;

void init() {
    for (int i = 1; i <= MAX_N; i++) {
        parent[i] = i;
        t[i] = 1;
    }
}

int root(int u) {
    if (parent[u] == u) {
        return u;
    }
    return parent[u] = root(parent[u]);
}

bool areJoined(int u, int v) {
    return root(u) == root(v);
}

void unite(int u, int v) {
    u = root(u);
    v = root(v);
    if (u != v) {
        if (t[u] < t[v]) {
            swap(u, v);
        }
        parent[v] = parent[u];
        t[v] += t[u];
    }
}

int main() {
    ifstream fin("adunare.in");
    ofstream fout("adunare.out");
    int a, b;
    fin >> a >> b;
    for (int i = 1; i <= a + b; i++) {
        edges.push_back(Edge {i, i + 1, 1});
    }
    init();
    int answer = 0;
    for (Edge e : edges) {
        if (areJoined(e.u, e.v) == false) {
            unite(e.u, e.v);
            answer += e.cost;
        }
    }
    fout << answer;
    return 0;
}