Submission #676958

#	Time	Username	Problem	Language	Result	Execution time	Memory
676958		KKT89	Love Polygon (BOI18_polygon)	C++17	100 / 100	188 ms	15648 KiB

polygon

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myrand(ll B){
    return (ull)rng() % B;
}
inline double time() {
    return static_cast<long double>(chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now().time_since_epoch()).count()) * 1e-9;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    map<string,int> mp;
    auto id = [&](string s)->int{
        if(mp.find(s) != mp.end()){
            return mp[s];
        }
        int sz = mp.size();
        mp[s] = sz; return sz;
    };
    vector<int> g(n,-1);
    vector<int> deg(n);
    vector<int> res(n,-1);
    for (int i = 0; i < n; ++i) {
        string s,t; cin >> s >> t;
        int x = id(s), y = id(t);
        g[x] = y;
        deg[y]++;
    }
    if(n%2){
        cout << -1 << endl;
        return 0;
    }
    vector<vector<int>> v(n);
    vector<pair<int,int>> pr;
    queue<int> q;
    for (int i = 0; i < n; ++i) {
        if(deg[i] == 0){
            q.push(i);
        }
    }
    while (q.size()){
        int s = q.front(); q.pop();
        int t = g[s];
        pr.push_back({s,t});
        deg[t]--;
        if(deg[t] == 0) q.push(t);
    }
    for(auto p:pr){
        auto [x,y] = p;
        if(deg[y] != 0){
            if(res[x] == -1) v[y].push_back(x);
        }
        else{
            if(res[x] == -1){
                if(res[y] == -1){
                    res[x] = 0;
                    res[y] = 1;
                }
                else{
                    res[x] = 1;
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if(res[i] != -1 or deg[i] == 0) continue;
        vector<int> cyc;
        int cur = i;
        do{
            cyc.push_back(cur);
            res[cur] = 0;
            for(int j:v[cur]){
                res[j] = 0;
            }
            cur = g[cur];
        } while (cur != i);
        int opt = 1e9;
        int m = cyc.size();
        if(m == 2){
            opt = v[cyc[0]].size() + v[cyc[1]].size();
            ans += opt;
            continue;
        }
        {
            vector<int> dp(m+1,1e9);
            dp[0] = 0;
            for (int j = 0; j < m; ++j) {
                if(j+1 < m){
                    dp[j+2] = min(dp[j+2], dp[j]+1+(int)v[cyc[j]].size()+(int)v[cyc[j+1]].size());
                }
                dp[j+1] = min(dp[j+1], dp[j]+1+(int)v[cyc[j]].size());
                if(v[cyc[j]].size()){
                    dp[j+1] = min(dp[j+1], dp[j]+1+(int)v[cyc[j]].size()-1);
                }
            }
            opt = min(opt, dp[m]);
        }
        reverse(cyc.begin(), cyc.end());
        int c = cyc.back(); cyc.pop_back();
        reverse(cyc.begin(), cyc.end()); cyc.push_back(c);
        {
            vector<int> dp(m+1,1e9);
            dp[0] = 0;
            for (int j = 0; j < m; ++j) {
                if(j+1 < m){
                    dp[j+2] = min(dp[j+2], dp[j]+1+(int)v[cyc[j]].size()+(int)v[cyc[j+1]].size());
                }
                dp[j+1] = min(dp[j+1], dp[j]+1+(int)v[cyc[j]].size());
                if(v[cyc[j]].size()){
                    dp[j+1] = min(dp[j+1], dp[j]+1+(int)v[cyc[j]].size()-1);
                }
            }
            opt = min(opt, dp[m]);
        }
        ans += opt;
    }
    for (int i = 0; i < n; ++i) {
        ans += res[i];
    }
    cout << ans << endl;
}

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