Submission #1054605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054605		cot7302	Love Polygon (BOI18_polygon)	C++17	100 / 100	49 ms	15768 KiB

polygon

#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)
using namespace std;
using i64 = long long;

template <class T>
using vec = vector<T>;

vec<int> get_input(int n) {
    unordered_map<string, int> id;
    auto get_id = [&](const string& str) -> int {
        if (auto it = id.find(str); it != end(id))
            return it->second;
        int sz = size(id);
        return id[str] = sz;
    };
    vec<int> ret(n);
    for (int i = 0; i < n; i++) {
        string s, t; cin >> s >> t;
        ret[get_id(s)] = get_id(t);
    }
    return ret;
}

constexpr int inf = 1e9;

void solve1(int n) {
    if (n % 2 == 1)
        return void(cout << "-1\n");
    vec<int> to = get_input(n);
    vec<int> dp(1 << n, inf);
    dp[0] = 0;
    for (int mask = 1; mask < (1 << n); mask++) if (__builtin_popcount(mask) % 2 == 0) {
        for (int i = 0; i < n; i++) if ((mask >> i) & 1) {
            for (int j = 0; j < i; j++) if ((mask >> j) & 1) {
                dp[mask] = min(dp[mask], dp[mask ^ (1 << i) ^ (1 << j)] + (to[i] != j) + (to[j] != i));
            }
        }
    }
    cout << dp.back() << '\n';
}

void solve2(int n) {
    if (n % 2 == 1)
        return void(cout << "-1\n");
    vec<int> to = get_input(n);
    vec<bool> is_cir(n);
    vec<int> indeg(n), rt(n), sz(n);
    for (int i = 0; i < n; i++)
        ++indeg[to[i]];
    vec<vec<int>> G(n);
    {
        queue<int> q;
        for (int i = 0; i < n; i++)
            if (indeg[i] == 0)
                q.emplace(i);
        while (!empty(q)) {
            int x = q.front(); q.pop();
            G[to[x]].emplace_back(x);
            if (--indeg[to[x]] == 0)
                q.emplace(to[x]);
        }
    }
    vec<array<int, 2>> max_pair(n);
    for (int i = 0; i < n; i++) if (indeg[i]) {
        for (int x = i; indeg[x]; x = to[x]) {
            is_cir[x] = true;
            indeg[x] = 0;
            ++sz[i];
            auto dfs = [&](auto&& f, int y) -> void {
                rt[y] = x;
                for (auto nxt : G[y]) {
                    f(f, nxt);
                    max_pair[y][0] += max_pair[nxt][1];
                }
                for (auto nxt : G[y]) {
                    max_pair[y][1] = max(max_pair[y][1], max_pair[y][0] - max_pair[nxt][1] + max_pair[nxt][0] + 1);
                }
            };
            dfs(dfs, x);
            rt[x] = i;
        }
    }
    vec<array<int, 2>> dp0(n), dp1(n);
    vec<int> ans(n);
    for (int i = 0; i < n; i++) if (rt[i] == i) {
        if (sz[i] == 2) {
            ans[i] = 2 + max_pair[i][0] + max_pair[to[i]][0];
        }
        dp0[i][0] = max_pair[i][0];
        dp0[i][1] = -inf;
        dp1[i][0] = max_pair[i][0];
        dp1[i][1] = max_pair[i][1];
        int pre = i;
        for (int x = to[i], cnt = 1; cnt < sz[i]; x = to[x], ++cnt) {
            dp1[x][0] = max_pair[x][0] + dp1[pre][1];
            dp1[x][1] = max(max_pair[x][1] + dp1[pre][1], max_pair[x][0] + dp1[pre][0] + 1);
            if (pre != i) {
                dp0[x][0] = max_pair[x][0] + dp0[pre][1];
                dp0[x][1] = max(max_pair[x][1] + dp0[pre][1], max_pair[x][0] + dp0[pre][0] + 1);
            }
            else {
                dp0[x][0] = max_pair[x][0] + dp0[pre][0];
                dp0[x][1] = max(max_pair[x][1] + dp0[pre][0], max_pair[x][0] + dp0[pre][0]);
            }
            if (cnt == sz[i] - 1) {
                ans[i] = max({ans[i], dp0[x][1], dp1[x][0], dp1[x][1]});
                ans[i] = max(ans[i], dp0[x][0] + 1);
            }
            pre = x;
        }
        if (sz[i] == 1)
            ans[i] = max(max_pair[i][0], max_pair[i][1]);
    }
    int tot{};
    for (int i = 0; i < n; i++)
        if (rt[i] == i)
            tot += ans[i];
    cout << n - tot << '\n';
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n; cin >> n;
    /*if (n <= 20) solve1(n);
    else */solve2(n);
}

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