Submission #939941

#	Time	Username	Problem	Language	Result	Execution time	Memory
939941		Warinchai	Love Polygon (BOI18_polygon)	C++14	29 / 100	287 ms	24196 KiB

polygon

#include<bits/stdc++.h>
using namespace std;
map<string,int>mp;
vector<int>v[100005];
vector<int>rt;
int dp[100005][2];
int dp2[100005][2];
int sz[100005];
int vis[100005];
int lp=0;
int p[100005];
int com[100005];
int fp(int a){return p[a]==a?a:p[a]=fp(p[a]);}
void un(int a,int b){p[fp(b)]=fp(a);}
int lv[100005];
void dfs(int u,int rt){
    //cerr<<"node"<<u<<"\n";
    if(vis[u])return;
    vis[u]=1;
    int sum=0;
    sz[u]=1;
    for(auto x:v[u]){
        if(vis[x])continue;
        dfs(x,rt);
        sz[u]+=sz[x];
        sum+=dp[x][0];
    }
    dp[u][1]=sum;
    for(auto x:v[u])if(x!=rt)dp[u][0]=max(sum-dp[x][0]+dp[x][1]+1,dp[u][0]);
}
void dfs2(int u,int p=0){
    lv[u]=lv[p]+1;
    if(u==lp)return;
    int sum=0;
    for(auto x:v[u]){
        dfs2(x,u);
        sum+=dp2[x][0];
    }
    dp2[u][1]=sum;
    for(auto x:v[u])dp2[u][0]=max(sum-dp2[x][0]+dp2[x][1]+1,dp2[u][0]);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    int cur=0;
    for(int i=1;i<=n;i++)p[i]=i;
    for(int i=0;i<n;i++){
        string a,b;cin>>a>>b;
        if(mp[a]==0)cur++,mp[a]=cur;
        if(mp[b]==0)cur++,mp[b]=cur;
        //cerr<<a<<" "<<mp[a]<<","<<b<<" "<<mp[b]<<"\n";
        if(mp[a]==mp[b])rt.push_back(mp[a])/*,cerr<<"root\n"*/;
        else if(fp(mp[a])==fp(mp[b]))rt.push_back(mp[a]),com[mp[a]]=mp[b]/*,cerr<<"one loop\n"*/;
        else v[mp[b]].push_back(mp[a])/*,cerr<<"nothing\n"*/;
        un(mp[a],mp[b]);
    }
    if(n%2==1){
        cout<<"-1";
        return 0;
    }
    /*for(int i=1;i<=n;i++){
        cerr<<i<<": ";
        for(auto x:v[i])cerr<<x<<" ";
        cerr<<"\n";
    }*/
    int ans=0;
    //for(auto x:rt)cerr<<x<<" ";
    //cerr<<"\n";
    for(auto x:rt){
        //cerr<<x<<":\n";
        dfs(x,x);
        //cerr<<dp[x][0]<<" "<<dp[x][1]<<"\n";
        int temp=(max(dp[x][0],dp[x][1])+sz[x]-2*max(dp[x][0],dp[x][1]));
        //cerr<<"temp:"<<temp<<"\n";
        if(com[x]!=0){
            //cerr<<"loop\n";
            lp=com[x];
            //cerr<<lp<<"\n";
            dfs2(x);
            //cerr<<dp2[x][1]<<" "<<dp[lp][1]<<"\n";
            int pp=dp2[x][1]+dp[lp][1]+1;
            //cerr<<lv[lp]<<"\n";
            if(sz[x]!=2)ans+=min(temp,pp+(sz[x]-pp*2)-(lv[lp]==2?1:0));
        }else ans+=(max(dp[x][0],dp[x][1])+sz[x]-2*max(dp[x][0],dp[x][1]));
        //cerr<<max(dp[x][0],dp[x][1])<<"\n";
    }
    cout<<ans;
}

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