Submission #1054736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054736		fatman87878	Love Polygon (BOI18_polygon)	C++17	100 / 100	110 ms	23752 KiB

polygon

#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long

constexpr int maxN=1e5+5;

unordered_map<string,int> mp;

int n,cnt,adj[maxN],deg[maxN],subsz[maxN],odd[maxN],dp[2][maxN],cirdp[2][maxN],ans;

queue<int> q;

bitset<maxN> vis;

vector<int> jda[maxN];

void dfs(int now){
    subsz[now]=1;
    int sum=0;
    for(int i:jda[now])if(!deg[i]){
        dfs(i);
        sum+=dp[0][i];
        dp[1][now]+=max(dp[0][i],dp[1][i]);
    }
    for(int i:jda[now])if(!deg[i])dp[0][now]=max(dp[0][now],sum-dp[0][i]+dp[1][i]+1);
}

int main(){
    cin>>n;
    for(int i = 0;i<n;i++){
        string a,b;cin>>a>>b;
        if(!mp.count(a))mp[a]=cnt++;
        if(!mp.count(b))mp[b]=cnt++;
        adj[mp[a]]=mp[b];
        deg[mp[b]]++;
        jda[mp[b]].emplace_back(mp[a]);
    }
    if(n&1)return cout<<-1,0;
    ans=n;
    fill(subsz,subsz+n,1);
    for(int i = 0;i<n;i++)if(!deg[i])q.emplace(i);
    for(int u;!q.empty();){
        u=q.front(),q.pop();
        if(!(--deg[adj[u]]))q.emplace(adj[u]);
    }
    for(int i = 0;i<n;i++)if(deg[i])dfs(i);
    for(int i = 0;i<n;i++)if(deg[i]&&!vis[i]){
        if(adj[i]==i)ans-=max(dp[0][i],dp[1][i]),vis[i]=1;
        else if(adj[adj[i]]==i)ans-=dp[1][i]+dp[1][adj[i]]+2,vis[i]=1,vis[adj[i]]=1;
        else {
            int mxans=0;
            {
                int pos=adj[i],last=i;
                cirdp[0][i]=max(dp[0][i],dp[1][i]);
                cirdp[1][i]=dp[1][i];
                vis[i]=1;
                for(;pos!=i;last=pos,pos=adj[pos]){
                    vis[pos]=1;
                    cirdp[0][pos]=max(cirdp[1][last]+dp[1][pos]+1,cirdp[0][last]+max(dp[1][pos],dp[0][pos]));
                    cirdp[1][pos]=max(cirdp[0][last],cirdp[1][last])+dp[1][pos];
                }
                mxans=max(cirdp[0][last],cirdp[1][last]);
            }
            {
                int pos=adj[i],last=i;
                cirdp[0][i]=0;
                cirdp[1][i]=-1e9;
                for(;pos!=i;last=pos,pos=adj[pos]){
                    cirdp[0][pos]=max(cirdp[1][last]+dp[1][pos]+1,cirdp[0][last]+max(dp[1][pos],dp[0][pos]));
                    cirdp[1][pos]=max(cirdp[0][last],cirdp[1][last])+dp[1][pos];
                }
                cirdp[0][pos]=max(cirdp[1][last]+dp[1][pos]+1,cirdp[0][last]+max(dp[1][pos],dp[0][pos]));
                cirdp[1][pos]=max(cirdp[0][last],cirdp[1][last])+dp[1][pos];
                mxans=max({mxans,cirdp[0][pos],cirdp[1][pos]});
            }
            ans-=mxans;
        }
    }
    cout<<ans;
}

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