제출 #1269773

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269773		seoul_korea	Love Polygon (BOI18_polygon)	C++20	100 / 100	172 ms	9284 KiB

polygon

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <queue>

// Hàm tính chi phí cho một chu trình hoặc một chuỗi các node "mồ côi"
void process_remaining_structure(int start_node, int& cost, std::vector<bool>& paired, const std::vector<int>& loves) {
    // Bỏ qua nếu node này đã được xử lý
    if (paired[start_node]) {
        return;
    }

    // Đo độ dài của chu trình hoặc đường đi của các node chưa được ghép cặp
    int k = 0;
    int current_node = start_node;
    while (!paired[current_node]) {
        paired[current_node] = true;
        current_node = loves[current_node];
        k++;
    }

    // Thêm chi phí dựa trên độ dài k
    // Nếu k=1, đó là một node mồ côi hoặc một vòng lặp tự thân -> chi phí là 1
    if (k == 1) { 
        cost += 1;
    } 
    // Nếu k > 2, đó là một "đa giác tình yêu"
    else if (k > 2) { 
        cost += (k / 2) + (k % 2);
    }
    // Nếu k=2, đó là một mối quan hệ, nhưng nó đã phải được xử lý ở Giai đoạn 0.
    // Nếu nó đến được đây, có nghĩa là nó không phải là một mối quan hệ 0 chi phí ban đầu.
    // Tuy nhiên, logic của Giai đoạn 0 đảm bảo các cặp 0 chi phí không lọt vào đây.
    // Bất kỳ cặp k=2 nào được tìm thấy ở đây đều là một phần của chuỗi phức tạp hơn đã được đơn giản hóa.
    // Chi phí của nó vẫn là 0.
}

int main() {
    // Tăng tốc độ I/O
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    // Nếu N lẻ, không thể ghép cặp tất cả mọi người
    if (n % 2 != 0) {
        std::cout << -1 << std::endl;
        return 0;
    }

    std::map<std::string, int> name_to_id;
    int next_id = 0;
    // Hàm lambda để lấy hoặc tạo ID cho tên
    auto get_id = [&](const std::string& name) {
        if (name_to_id.find(name) == name_to_id.end()) {
            name_to_id[name] = next_id++;
        }
        return name_to_id[name];
    };

    std::vector<int> loves(n);
    std::vector<int> in_degree(n, 0);

    // Đọc input và xây dựng đồ thị
    for (int i = 0; i < n; ++i) {
        std::string s, t;
        std::cin >> s >> t;
        int id_s = get_id(s);
        int id_t = get_id(t);
        loves[id_s] = id_t;
        in_degree[id_t]++;
    }

    int cost = 0;
    std::vector<bool> paired(n, false);

    // *** GIAI ĐOẠN 0: Ưu tiên xử lý các cặp có sẵn (chi phí 0) ***
    for (int i = 0; i < n; ++i) {
        if (paired[i]) continue;
        int j = loves[i];
        // Kiểm tra xem j có yêu ngược lại i không, và j phải khác i
        if (i != j && loves[j] == i) {
            paired[i] = true;
            paired[j] = true;
        }
    }

    // *** GIAI ĐOẠN 1: Xử lý các đường đi từ node lá ***
    std::queue<int> q;
    for (int i = 0; i < n; ++i) {
        // Chỉ thêm các node lá CHƯA được ghép cặp
        if (!paired[i] && in_degree[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        // Node u có thể đã được ghép cặp trong một lần lặp trước đó
        if (paired[u]) {
            continue;
        }

        int v = loves[u];
        // Nếu mục tiêu v đã được ghép cặp (ví dụ ở Giai đoạn 0),
        // thì u trở thành mồ côi và sẽ được xử lý ở Giai đoạn 2.
        if (paired[v]) {
            continue;
        }

        // Ghép cặp u với v. Chi phí là 1 (cho v).
        cost += 1;
        paired[u] = true;
        paired[v] = true;

        // Cập nhật in-degree cho node mà v yêu
        int w = loves[v];
        in_degree[w]--;
        // Nếu w trở thành node lá và chưa được ghép cặp, thêm vào hàng đợi
        if (in_degree[w] == 0 && !paired[w]) {
            q.push(w);
        }
    }

    // *** GIAI ĐOẠN 2: Xử lý các chu trình và các node mồ côi còn lại ***
    for (int i = 0; i < n; ++i) {
        if (!paired[i]) {
            process_remaining_structure(i, cost, paired, loves);
        }
    }

    std::cout << cost << std::endl;

    return 0;
}

• Subtask 1: 21 / 21
• Subtask 2: 25 / 25
• Subtask 3: 29 / 29
• Subtask 4: 25 / 25