Submission #632260

#	Time	Username	Problem	Language	Result	Execution time	Memory
632260		jasmin	Love Polygon (BOI18_polygon)	C++14	75 / 100	292 ms	48728 KiB

polygon

#include<bits/stdc++.h>
using namespace std;
#define int long long

struct unionfind{
    vector<int> chef;
    vector<int> cnt;

    unionfind(int n){
        chef.resize(n);
        iota(chef.begin(), chef.end(), 0);
        cnt.resize(n, 1);
    }

    int find(int a){
        if(chef[a]==a) return a;
        return chef[a]=find(chef[a]);
    }
    void unite(int a, int b){
        if(find(a)==find(b)) return;
        cnt[find(b)]+=cnt[find(a)];
        chef[find(a)]=find(b);
    }
};

void dfs(int v, vector<vector<int> >& adi, vector<bool>& vis, unionfind& ufind, vector<int>& postorder, bool first){
    assert(!vis[v]);
    vis[v]=true;

    for(auto u: adi[v]){
        if(!vis[u]){
            dfs(u, adi, vis, ufind, postorder, first);
            if(!first){
                ufind.unite(u, v);
            }
        }
    }
    if(first){
        postorder.push_back(v);
    }
}

void kosaraju(int n, vector<vector<int> >& adi, vector<vector<int> >& rev, unionfind& ufind){
    vector<int> postorder;
    vector<bool> vis(n);
    for(int v=0; v<n; v++){
        if(!vis[v]) {
            dfs(v, adi, vis, ufind, postorder, true);
        }
    }
    vis.assign(n, false);
    for(int v=n-1; v>=0; v--){
        if(!vis[postorder[v]]) {
            dfs(postorder[v], rev, vis, ufind, postorder, false);
        }
    }
}

void dfs_dp(int v, vector<vector<int> >& adi, vector<vector<int> >& dp, vector<bool>& vis, unionfind& ufind){
    if(vis[v]) return;
    vis[v]=true;

    int add=0;
    if(ufind.cnt[v]!=2){
        add=(ufind.cnt[v]+1)/2;
    }

    int sum0=0;
    for(auto u: adi[v]){
        dfs_dp(u, adi, dp, vis, ufind);
        sum0+=dp[u][0];
    }
    dp[v][1]=sum0;
    dp[v][0]=sum0+add;

    for(auto u: adi[v]){
        if(ufind.cnt[v]%2==1){
            dp[v][0]=min(dp[v][0], sum0-dp[u][0]+dp[u][1]+add);
        }
    }

    //cout << v << " " << ufind.find(v) << " " << ufind.cnt[ufind.find(v)] << "\n";
    //cout << dp[v][0] << " " << dp[v][1] << "\n";
}

int solve(int n, vector<vector<int> >& adi_alt, vector<vector<int> >& rev, vector<int>& par){
    unionfind ufind(n);
    kosaraju(n, adi_alt, rev, ufind);

    vector<vector<int> > adi(n);
    for(int u=0; u<n; u++){
        int v=par[u];
        if(v==-1) continue;
        if(ufind.find(u)!=ufind.find(v)){
            adi[ufind.find(v)].push_back(ufind.find(u));
        }
    }

    /*for(int i=0; i<n; i++){
        cout << i << ": " << ufind.find(i) << "\n";
    }
    for(int i=0; i<n; i++){
        if(ufind.find(i)==i){
            cout << i << ": ";
            for(auto e: adi[i]){
                cout << e << " ";
            }
            cout << "\n";
        }
    }*/

    vector<bool> vis(n);
    vector<vector<int> > dp(n, vector<int> (2));
    int ans=0;
    for(int v=0; v<n; v++){
        if(vis[ufind.find(v)]) continue;

        if(ufind.find(v)!=v || par[v]==-1){
            dfs_dp(ufind.find(v), adi, dp, vis, ufind);
            ans+=dp[ufind.find(v)][0];
        }
    }
    return ans;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    int cnt=1;
    map<string, int> ind;
    vector<vector<int> > adi(n);
    vector<vector<int> > rev(n);
    vector<int> par(n, -1);
    for(int i=0; i<n; i++){
        string s, t;
        cin >> s >> t;
        if(ind[s]==0){
            ind[s]=cnt;
            cnt++;
        }
        if(ind[t]==0){
            ind[t]=cnt;
            cnt++;
        }

        int a=ind[s];
        int b=ind[t];
        if(a!=b){
            adi[b-1].push_back(a-1);
            rev[a-1].push_back(b-1);
            par[a-1]=b-1;
        }
    }

    if(n%2==1){
        cout << -1 << "\n";
        return 0;
    }

    cout << solve(n, adi, rev, par) << "\n";
}

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