Submission #1236304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236304		grossly_overconfident	Love Polygon (BOI18_polygon)	C++20	100 / 100	576 ms	76300 KiB

polygon

#ifndef FOAM_H
#define FOAM_H

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <cmath>
#include <set>
#include <cassert>
#include <map>
#include <fstream>
#include <unordered_set>
#include <unordered_map>
#include <list>
#include <climits>
#include <cstdlib>
#include <numeric>

#endif

class dp {
private:

    int n{};

    std::vector<std::vector<int>> cac{};
    std::vector<std::vector<int>> adj{};
    std::vector<bool> visited{};

    int solve(int i, int j, int p) {
        visited[i] = 1;
        if (cac[i][j] != -1) {
            return cac[i][j];
        }
        std::vector<std::vector<int>> neigh(adj[i].size(), std::vector<int>(2, 0));

        int total{ 0 };
        

        for (int k{ 0 }; k < adj[i].size(); ++k) {
            if (adj[i][k] == p) {
                continue;
            }
            neigh[k][0] = solve(adj[i][k], 0, i);
            neigh[k][1] = solve(adj[i][k], 1, i) + 1;
            total += neigh[k][0];
        }
        int best{ total };
        if (j == 0) {
            for (int k{ 0 }; k < adj[i].size(); ++k) {
                if (adj[i][k] == p) {
                    continue;
                }
                best = std::max(best, total - neigh[k][0] + neigh[k][1]);
            }
        }
        return cac[i][j] = best;
        
    }

public:
    dp(int N, std::vector<std::vector<int>> ADJ) : n{ N }, adj{ ADJ } {
        cac.assign(N, std::vector<int>(2, -1));
        visited.resize(n, 0);
    }

    std::vector<int> get() {
        std::vector<int> out{};
        for (int i{ 0 }; i < n; ++i) {
            if (!visited[i]) {
                out.push_back(solve(i, 0, i));
            }
        }
        return out;
    }

};

void dfs(int i, std::vector<int>& link, std::vector<int>& visited, int v, std::vector<int>& loop) {
    if (visited[i] != -1) {
        return;
    }
    visited[i] = v;
    if (visited[link[i]] == v) {
        loop[v] = i;
    }
    dfs(link[i], link, visited, v, loop);
    visited[i] = visited[link[i]];
}

int main() {

    int n{};
    std::cin >> n;

    if (n & 1) {
        std::cout << -1;
        return 0;
    }

    std::map<std::string, int> b;

    std::vector<int> link(n);
    
    int id{ 0 };
    for (int i{ 0 }; i < n; ++i) {
        std::string x{}, y{};
        std::cin >> x >> y;
        if (!b.count(x)) {
            b[x] = id++;
        }
        if (!b.count(y)) {
            b[y] = id++;
        }
        link[b[x]] = b[y];
    }

    std::vector<int> visited(n, -1);
    std::vector<int> loop(n, -1);

    for (int i{ 0 }; i < n; ++i) {
        dfs(i, link, visited, i, loop);
    }


    std::vector<std::vector<int>> clumps(n);
    for (int i{ 0 }; i < n; ++i) {
        clumps[visited[i]].push_back(i);
    }

    std::vector<std::vector<int>> option1(n), option2(n);
    int twocycles{ 0 };
    for (int i{ 0 }; i < n; ++i) {
        bool twocycleflag{ 0 };
        if (clumps[i].empty()) {
            continue;
        }
        if (link[link[loop[i]]] == loop[i] && link[loop[i]] != loop[i]) {
            twocycles++;
            twocycleflag = 1;
        }
        


        for (auto k : clumps[i]) {
            if (link[k] == k) {
                continue;
            }
            if (twocycleflag) {
                if (link[k] == loop[i] || link[k] == link[loop[i]]) {
                    continue;
                }
            }
            if (k != loop[i]) {
                option1[k].push_back(link[k]);
                option1[link[k]].push_back(k);
            }
            if (k != link[loop[i]]) {
                option2[k].push_back(link[k]);
                option2[link[k]].push_back(k);
            }
            
        }
    }

    dp solver1(n, option1), solver2(n, option2);

    int total{ twocycles * 2 };

    std::vector<int> x{ solver1.get() }, y{ solver2.get() };

    for (int i{ 0 }; i < x.size(); ++i) {
        total += std::max(x[i], y[i]);
    }
    std::cout << n - total;

    
    return 0;
}

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