Submission #1269770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269770		seoul_korea	Love Polygon (BOI18_polygon)	C++20	54 / 100	164 ms	9348 KiB

polygon

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

// Calculates the minimum arrows needed for a cycle of unpaired nodes.
void process_cycle(int start_node, int& cost, std::vector<bool>& paired, const std::vector<int>& loves) {
    if (paired[start_node]) {
        return;
    }

    // Traverse to find the cycle and its length
    int k = 0;
    int current_node = start_node;
    while (!paired[current_node]) {
        paired[current_node] = true;
        current_node = loves[current_node];
        k++;
    }

    // Add cost based on cycle length k
    if (k == 1) { // Self-love cycle
        cost += 1;
    } else if (k > 2) { // Love polygon
        cost += (k / 2) + (k % 2);
    }
    // For k=2 (a relationship), the cost is 0.
}

int main() {
    // Fast I/O
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    // If N is odd, it's impossible to pair everyone.
    if (n % 2 != 0) {
        std::cout << -1 << std::endl;
        return 0;
    }

    std::map<std::string, int> name_to_id;
    int next_id = 0;
    // Helper lambda to get or create an ID for a name
    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);

    // Read input and build the graph
    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);
    std::queue<int> q;

    // Initialize queue with all leaf nodes (in-degree 0)
    for (int i = 0; i < n; ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }

    // Phase 1: Greedily process paths starting from leaves
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        if (paired[u]) {
            continue;
        }

        int v = loves[u];
        if (paired[v]) {
            // u is an "orphan" as its target v is already paired.
            // u must be shot. This single operation costs 1 arrow.
            cost += 1;
            paired[u] = true;
            continue;
        }

        // Greedily pair leaf u with its target v. Cost is 1 arrow for v.
        cost += 1;
        paired[u] = true;
        paired[v] = true;

        // Since v is now paired, update the in-degree of its original target.
        int w = loves[v];
        in_degree[w]--;
        if (in_degree[w] == 0) {
            q.push(w);
        }
    }

    // Phase 2: Process remaining nodes, which must form cycles.
    for (int i = 0; i < n; ++i) {
        if (!paired[i]) {
            process_cycle(i, cost, paired, loves);
        }
    }

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

    return 0;
}

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