Submission #891212

#	Time	Username	Problem	Language	Result	Execution time	Memory
891212		Dec0Dedd	Love Polygon (BOI18_polygon)	C++14	46 / 100	289 ms	19112 KiB

polygon

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<string, string> pii;
 
const int N = 1e5+10;
const int INF = 1e6;
 
int ind[N], ed[N], n;
 
map<string, int> sc;
set<string> st;
 
bool vis[N];
 
int dfs(int v) {
    vis[v]=true;
    if (vis[ed[v]]) return 1;
    return 1+dfs(ed[v]);
}
 
bool checksub2() {
    for (int i=1; i<=n; ++i) {
        if (ind[i] != 1) return false;
    } return true;
}
 
int solvesub2() {
    // everything's a cycle
    int cnt=0, ans=0;
    for (int i=1; i<=n; ++i) {
        if (vis[i]) continue;
        int sz=dfs(i);
 
        if (sz == 2) continue;
 
        ans+=sz/2;
        if (sz%2) ++cnt;
    } ans+=cnt;
    return ans;
}
 
bool checksub1() {
    return n <= 20;
}
 
int dp[1<<20];
bool vis2[1<<20];
 
int edg(int a, int b) {
    return 2-(ed[a]==b)-(ed[b]==a);
}
 
int ssb1(int msk) {
    if (vis2[msk]) return dp[msk];
    if (msk == 0) return 0;
    vis2[msk]=true, dp[msk]=INF;
 
    vector<int> v;
    for (int i=0; i<n; ++i) {
        if (msk&(1<<i)) v.push_back(i);
    } int sz=v.size();
    for (int i=0; i<sz; ++i) {
        for (int j=i+1; j<sz; ++j) {
            dp[msk]=min(dp[msk], ssb1(msk^(1<<v[i])^(1<<v[j]))+edg(v[i]+1, v[j]+1));
        }
    } return dp[msk];
}
 
int solvesub1() {
    return ssb1((1<<n)-1);
}
 
// no cycles
bool checksub3() {
    return true;
}

int dfss(int v, bool ss) {
    vis[v]=true;
 
    if (ed[v] == v) return 0;
    if (vis[ed[v]]) return 0;
    if (ss) return dfss(ed[v], false);
    return dfss(ed[v], true)+1;
}
 
int solvesub3() {
    memset(vis, false, sizeof(vis));
 
    int res=0;
    for (int i=1; i<=n; ++i) {
        if (vis[i]) continue;
        if (ind[i] == 0) res+=dfss(i, false);
    }
    
    return res+(n-2*res); 
}
 
void solve() {
    cin>>n;
 
    int c=1;
    for (int i=1; i<=n; ++i) {
        string a, b; cin>>a>>b;
        if (st.find(a) == st.end()) sc[a]=c++;
        st.insert(a);
        if (st.find(b) == st.end()) sc[b]=c++;
        st.insert(b);
 
        int ap=sc[a], bp=sc[b];
        ed[ap]=bp;
        ++ind[bp];
    }
 
    if (n%2) {
        cout<<-1<<"\n";
        return;
    }
 
    if (checksub2()) cout<<solvesub2()<<"\n";
    else if (checksub1()) cout<<solvesub1()<<"\n";
    else if (checksub3()) cout<<solvesub3()<<"\n";
    else cout<<-1<<"\n";
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int t=1;
    while (t--) solve();
}

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