Submission #486646

#	Time	Username	Problem	Language	Result	Execution time	Memory
486646		FatihSolak	Love Polygon (BOI18_polygon)	C++17	75 / 100	2188 ms	1033428 KiB

polygon

#include <bits/stdc++.h>
#define N 200005
using namespace std;
vector<int> adj[N];
int ans = 0;
int edge[N];
bool cycle[N];
int vis[N];
bool del[N];
void dfs(int v){
    vis[v] = 1;
    if(vis[edge[v]] == 1){
        cycle[v] = 1;
        int tmp = edge[v];
        while(tmp != v){
            cycle[tmp] = 1;
            tmp = edge[tmp];
        }
    }
    else if(!vis[edge[v]]){
        dfs(edge[v]);
    }
    vis[v] = 2;
}
void dfs2(int v){
    for(auto u:adj[v]){
        if(cycle[u])continue;
        dfs2(u);
        ans += !del[u];
        if(!del[u]){
            del[v] = del[u] = 1;
        }
    }
}
void solve(){
    int n;
    cin >> n;
    int cnt = 1;
    map<string,int>val;
    for(int i=1;i<=n;i++){
        string s,t;
        cin >> s >> t;
        if(!val[s])val[s] = cnt++;
        if(!val[t])val[t] = cnt++;
        edge[val[s]] = val[t];
        adj[val[t]].push_back(val[s]);
    }
    if(n%2){
        cout << -1 << endl;
        return;
    }
    if(n <= 20){
        int ans = n;
        for(int mask = 0;mask < (1<<(n+1));mask+=2){
            vector<int> go(n+1);
            bool ok = 1;
            for(int i=1;i<=n;i++){
                if(mask & (1<<i)){
                    if(edge[i] == i)ok = 0;
                    if(go[i] && edge[i] != go[i])ok = 0;
                    go[i] = edge[i];
                    if(go[edge[i]] && go[edge[i]] != i)ok = 0;
                    go[edge[i]] = i;
                }
            }
            if(ok)
                ans = min(ans,n - __builtin_popcount(mask));
        }
        cout << ans;
        return;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            dfs(i);
        }
    }
    /*
    for(auto u:val){
        cout << u.first << " " << u.second << endl;
    }*/
    for(int i=1;i<=n;i++){
        if(cycle[i]){
            dfs2(i);
        }
    }
    /*
    for(auto u:val){
        cout << u.first << " " << del[u.second] << endl;
    }*/
    ///cout << ans << endl;
    for(int i=1;i<=n;i++){
        if(del[i])continue;
        //cout << i << endl;
        vector<int> v;
        int tmp = i;
        while(v.empty() || tmp != i){
            v.push_back(tmp);
            if(!del[edge[tmp]])
                tmp = edge[tmp];
            else break;
        }
        if(tmp == i){
            if(v.size() != 2){
                ans += v.size()/2 + v.size()%2;
            }
            for(auto u:v)del[u] = 1;
            continue;
        }
        int bef = -1;
        for(auto u:adj[i]){
            if(!del[u])bef = u;
        }
        while(bef != -1){
            v.push_back(bef);
            for(auto u:adj[bef]){
                if(!del[u]){
                    bef = u;
                    break;
                }
            }
        }
        for(auto u:v)del[u] = 1;
        ans += v.size()/2 + v.size()%2;
    }
    cout << ans;

}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

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