Submission #1133277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133277		vladilius	Love Polygon (BOI18_polygon)	C++20	100 / 100	192 ms	36412 KiB

polygon

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, cc = 0; cin>>n;
    if (n % 2){
        cout<<-1<<"\n";
        return 0;
    }
    map<string, int> mp;
    vector<int> f(n + 1);
    for (int i = 1; i <= n; i++){
        string s, t; cin>>s>>t;
        if (mp.find(s) == mp.end()){
            mp[s] = ++cc;
        }
        if (mp.find(t) == mp.end()){
            mp[t] = ++cc;
        }
        f[mp[s]] = mp[t];
    }

    vector<int> g[n + 1];
    vector<bool> ban(n + 1);
    for (int i = 1; i <= n; i++){
        if (f[f[i]] == i){
            if (f[i] != i){
                ban[i] = 1;
            }
            continue;
        }
        g[i].pb(f[i]);
        g[f[i]].pb(i);
    }
    
    vector<bool> used(n + 1);
    vector<int> d[n + 1], all;
    pii t;
    function<void(int, int)> dfs = [&](int v, int pr){
        used[v] = 1; all.pb(v);
        for (int i: g[v]){
            if (i == pr || ban[i]) continue;
            if (used[i]){
                t = {v, i};
                continue;
            }
            d[i].pb(v);
            d[v].pb(i);
            dfs(i, v);
        }
    };
    
    vector<vector<int>> dp(n + 1, vector<int>(2));
    function<void(int, int)> solve = [&](int v, int pr){
        used[v] = 1;
        for (int i: d[v]){
            if (i == pr || ban[i]) continue;
            solve(i, v);
            dp[v][0] += max(dp[i][0], dp[i][1]);
        }
        for (int i: d[v]){
            if (i == pr || ban[i]) continue;
            dp[v][1] = max(dp[v][1], 1 + dp[i][0] + (dp[v][0] - max(dp[i][0], dp[i][1])));
        }
    };
    
    int out = n;
    for (int i = 1; i <= n; i++){
        if (ban[i]){
            out--;
            continue;
        }
        if (used[i]) continue;
        all.clear();
        t = {0, 0};
        dfs(i, 0);
        solve(i, 0);
        int d1 = max(dp[i][0], dp[i][1]);
        
        if (t.ff){
            int d2 = 1;
            for (int j: all) dp[j][0] = dp[j][1] = used[j] = 0;
            used[t.ff] = used[t.ss] = ban[t.ff] = ban[t.ss] = 1;
            for (int j: all){
                if (used[j]) continue;
                solve(j, 0);
                d2 += max(dp[j][0], dp[j][1]);
            }
            ban[t.ff] = ban[t.ss] = 0;
            out -= max(d1, d2);
        }
        else {
            out -= d1;
        }
    }
    
    cout<<out<<"\n";
}

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