Submission #3664960

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n,k;
  cin>>n>>k;
  vector<Int> a(n),b(n);
  for(Int i=0;i<n;i++) cin>>a[i];
  for(Int i=0;i<n;i++) cin>>b[i];
  vector<Int> c(n+1,0);
  Int sum=0;
  vector<multiset<Int> > G(n+1);
  for(Int i=0;i<n;i++){
    if(a[i]>b[i]) swap(a[i],b[i]);
    c[b[i]]++;
    sum+=b[i];
    if(b[i]!=a[i]) G[b[i]].emplace(a[i]);
  }
  Int cnt=0;
  for(Int i=1;i<=n;i++) cnt+=c[i]>0;
  while(cnt<k){
    const Int INF = 1e15;
    vector<Int> dp(n+1,INF),pr(n+1,-1);
    using P = pair<Int, Int>;
    priority_queue<P,vector<P>, greater<P> > pq;
    for(Int i=1;i<=n;i++){
      if(c[i]<=1) continue;
      dp[i]=i;
      pq.emplace(i,i);
    }
    while(!pq.empty()){
      Int d,v;
      tie(d,v)=pq.top();pq.pop();
      if(dp[v]<d) continue;
      for(Int u:G[v]){
        if(dp[u]<=dp[v]) continue;
        dp[u]=dp[v];
        pr[u]=v;
        pq.emplace(dp[u],u);
      }
    }
    
    Int v=-1;
    for(Int i=1;i<=n;i++){
      if(c[i]!=0) continue;
      if(v<0||(dp[v]-v>dp[i]-i)) v=i;
    }
    
    {
      sum-=dp[v]-v;
      cnt++;
      Int u=pr[v];
      while(~u){
        c[v]++;
        c[u]--;
        G[u].erase(G[u].find(v));
        G[v].emplace(u);
        v=u;
        u=pr[u];
      }      
    }
  }
  cout<<sum<<endl;
  return 0;
}

Submission Info

Judge Result