oj.uz

Submission #939941

# Submission time Handle Problem Language Result Execution time Memory
939941 2024-03-07T02:00:33 Z Warinchai Love Polygon (BOI18_polygon) C++14
29 / 100
 287 ms 24196 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5980 KB Output is correct
2 Correct 1 ms 5980 KB Output is correct
3 Correct 2 ms 6232 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Correct 2 ms 5980 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Incorrect 2 ms 5980 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5976 KB Output is correct
2 Correct 1 ms 5980 KB Output is correct
3 Correct 1 ms 5980 KB Output is correct
4 Incorrect 269 ms 24012 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 16220 KB Output is correct
2 Correct 266 ms 18340 KB Output is correct
3 Correct 193 ms 14280 KB Output is correct
4 Correct 243 ms 15484 KB Output is correct
5 Correct 287 ms 24196 KB Output is correct
6 Correct 266 ms 15452 KB Output is correct
7 Correct 257 ms 15520 KB Output is correct
8 Correct 207 ms 15344 KB Output is correct
9 Correct 231 ms 14928 KB Output is correct
10 Correct 178 ms 14284 KB Output is correct
11 Correct 2 ms 5976 KB Output is correct
12 Correct 1 ms 5980 KB Output is correct
13 Correct 2 ms 5980 KB Output is correct
14 Correct 1 ms 5980 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5980 KB Output is correct
2 Correct 1 ms 5980 KB Output is correct
3 Correct 2 ms 6232 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Correct 2 ms 5980 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Incorrect 2 ms 5980 KB Output isn't correct
8 Halted 0 ms 0 KB -