Submission #891215

#	Time	Username	Problem	Language	Result	Execution time	Memory
891215		Dec0Dedd	Love Polygon (BOI18_polygon)	C++14	75 / 100	282 ms	32884 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;
vector<int> GT[N];
 
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;
}

bool usd[N];
int dfss(int v, int p=-1) {
    vis[v]=true;

    int x=0;
    for (auto u : GT[v]) {
        if (vis[u]) continue;
        x+=dfss(u, v);
    }

    if (p != -1 && !usd[v] && !usd[p]) {
        usd[v]=usd[p]=true;
        ++x;
    } return x;
}
 
int solvesub3() {
    memset(vis, false, sizeof(vis));
    memset(usd, false, sizeof(usd));

    int res=0;
    for (int i=1; i<=n; ++i) {
        if (ed[i] != i) continue;
        res+=dfss(i);
    } return n-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;
        GT[bp].push_back(ap);
        ++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: 29 / 29
• Subtask 4: 0 / 25