Submission #680500

#	Time	Username	Problem	Language	Result	Execution time	Memory
680500		jhwest2	Love Polygon (BOI18_polygon)	C++17	100 / 100	355 ms	36156 KiB

polygon

#include <bits/stdc++.h>
using namespace std;

const int N = 101010;
int n, go[N], vis[N], done[N]; bool dead[N];
vector<int> g[N];

map<string, int> mp;
map<int, int> cant;

array<int, 3> dfs(int p, int v) {
    int s = 0, t = 1, sz = 1;
    done[v]++;
    for (int x : g[v]) {
        if (p == x || dead[x])
            continue;
        if (cant[v] == x)
            continue;
        
        auto [y, z, w] = dfs(v, x);
        s += max(y, z);
        t += y;
        sz += w;
    }
    return {s, t, sz};
}
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n;
    int sz = 0;
    for (int i = 1; i <= n; i++) {
        string s, t; cin >> s >> t;
        int u = (mp[s] = (mp[s]) ? mp[s] : ++sz);
        int v = (mp[t] = (mp[t]) ? mp[t] : ++sz);
        go[u] = v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    if (n % 2 == 1) 
        return !(cout << -1);

    int ans = 0;
    vector<int> vtx;
    for (int i = 1; i <= n; i++) {
        if (vis[i] == 2) 
            continue;

        int v = i;
        while (!vis[v]) {
            vtx.push_back(v);
            vis[v] = 1;
            v = go[v];
        }
        if (vis[v] == 1) {
            // not using the edge
            int s = 0;

            cant[go[v]] = v;
            cant[v] = go[v];
            auto [x, y, z] = dfs(v, v); 
            s = z - max(x, y);

            // using the edge
            if (go[v] != v) {
                int t = 1;

                // cycle is length 2
                if (v == go[go[v]])
                    t = 2;

                dead[v] = 1;
                dead[go[v]] = 1;
                
                for (int x : g[v])
                    if (go[v] != x) {
                        auto [a, b, c] = dfs(v, x);
                        t += c - max(a, b);
                    }
                for (int x : g[go[v]]) 
                    if (v != x && done[x] != 2) {
                        auto [a, b, c] = dfs(go[v], x);
                        t += c - max(a, b);
                    }
                
                ans += max(s, t);
            }
            else
                ans += s;
        }

        // initialize
        for (int x : vtx)
            vis[x] = 2;
        vector<int>().swap(vtx);
    }
    cout << n - ans;
}

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