Submission #676697

#	Time	Username	Problem	Language	Result	Execution time	Memory
676697		Cyanmond	Love Polygon (BOI18_polygon)	C++17	100 / 100	334 ms	27064 KiB

polygon

#include <bits/stdc++.h>

void chmax(int &a, int b) {
    a = std::max(a, b);
}

int main() {
    int N;
    std::cin >> N;
    if (N % 2 == 1) {
        std::cout << -1 << std::endl;
        return 0;
    }
    std::vector<std::vector<int>> namori(N), r_namori(N);
    std::map<std::string, int> index_map;

    auto get_index = [&](std::string x) {
        if (index_map.find(x) == index_map.end()) {
            return index_map[x] = (int)index_map.size();
        } else {
            return index_map[x];
        }
    };

    for (int i = 0; i < N; ++i) {
        std::string a, b;
        std::cin >> a >> b;
        const int x = get_index(a), y = get_index(b);
        namori[x].push_back(y);
        r_namori[y].push_back(x);
    }

    std::vector<bool> seen(N);

    auto calc_max_matching = [&](auto &&self, const int root, const int p) -> std::pair<int, bool> {
        seen[root] = true;
        bool used = false;
        int ret = 0;
        for (const int t : r_namori[root]) {
            if (t == p) {
                continue;
            }
            const auto [sum, b] = self(self, t, root);
            ret += sum;
            if (not b and not used) {
                used = true;
                ++ret;
            }
        }
        return std::make_pair(ret, used);
    };

    int answer = 0;
    for (int f = 0; f < N; ++f) {
        if (seen[f]) {
            continue;
        }

        // find cycle
        std::vector<int> cycle;
        auto find_cycle = [&](auto &&self, const int v) -> bool {
            cycle.push_back(v);
            if (seen[v]) {
                return true;
            }
            seen[v] = true;
            for (const int t : namori[v]) {
                if (self(self, t)) {
                    return true;
                }
            }
            cycle.pop_back();
            return false;
        };
        find_cycle(find_cycle, f);
        cycle.erase(cycle.begin(), std::find(cycle.begin(), cycle.end(), cycle.back()) + 1);

        // greedy matching
        const int m = (int)cycle.size();
        std::vector<std::pair<int, int>> vals(m);
        for (int i = 0; i < m; ++i) {
            const int v = cycle[i];
            vals[i].first = calc_max_matching(calc_max_matching, v, cycle[(i - 1 + m) % m]).first;
            int sum = 0;
            for (const int t : r_namori[v]) {
                if (t == cycle[(i - 1 + m) % m]) {
                    continue;
                }
                sum += calc_max_matching(calc_max_matching, t, v).first;
            }
            vals[i].second = sum;
        }

        // dp
        auto calc_dp = [&](std::vector<std::pair<int, int>> data) {
            std::vector<std::pair<int, int>> dp(m + 1, {-N, -N});
            dp[0].first = 0;
            for (int i = 0; i < m; ++i) {
                chmax(dp[i + 1].first, dp[i].first + data[i].first);
                chmax(dp[i + 1].first, dp[i].second + data[i].second + 1);
                chmax(dp[i + 1].second, dp[i].first + data[i].second);
                if (cycle.size() == 2) {
                    chmax(dp[i + 1].first, dp[i].second + data[i].second + 2);
                }
                chmax(dp[i + 1].first, dp[i + 1].second);
            }
            return dp[m].first;
        };

        int res = calc_dp(vals);
        vals.push_back(vals[0]);
        vals.erase(vals.begin());
        chmax(res, calc_dp(vals));
        answer += res;
    }

    std::cout << N - answer << std::endl;
}

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