Submission #68601988

---

Source Code Expand

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long int ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<vvvl> vvvvl;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
typedef vector<vvvb> vvvvb;
typedef pair<ll,ll> pl;
typedef pair<ll,pl> ppl;
typedef pair<ll,ppl> pppl;
typedef pair<ll,pppl> pppppl;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) begin(a),end(a)
#define sz(a) (int)(a).size()
#define F first
#define S second
#define bs(A,x) binary_search(all(A),x)
#define lb(A,x) (ll)(lower_bound(all(A),x)-A.begin())
#define ub(A,x) (ll)(upper_bound(all(A),x)-A.begin())
#define cou(A,x) (ll)(upper_bound(all(A),x)-lower_bound(all(A),x))
template<typename T>using min_priority_queue=priority_queue<T,vector<T>,greater<T>>;
template<class T>bool chmax(T&a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T&a,T b){if(b<a){a=b;return 1;}return 0;}
//*
using mint=modint998244353;
const ll mod=998244353;
//*/
/*
using mint=modint1000000007;
const ll mod=1000000007;
//*/
//using mint=modint;
//*
typedef vector<mint> vm;
typedef vector<vm> vvm;
typedef vector<vvm> vvvm;
typedef vector<vvvm> vvvvm;
ostream&operator<<(ostream&os,mint a){os<<a.val();return os;}
istream&operator>>(istream&is,mint&a){int x;is>>x;a=mint(x);return is;}
//*/
template<typename T1,typename T2>ostream&operator<<(ostream&os,pair<T1,T2>p){os<<p.F<<" "<<p.S;return os;}
template<typename T1,typename T2>istream&operator>>(istream&is,pair<T1,T2>&p){is>>p.F>>p.S;return is;}
template<typename T>ostream&operator<<(ostream&os,vector<T>v){rep(i,0,sz(v))os<<v[i]<<(i+1!=sz(v)?" ":"");return os;}
template<typename T>istream&operator>>(istream&is,vector<T>&v){for(T&in:v)is>>in;return is;}
int main(){
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);
  ll N;cin>>N;
  vl P(N);cin>>P;
  rep(i,0,N)P[i]--;
  vl C;
  {
    dsu G(N);
    rep(i,0,N)G.merge(i,P[i]);
    auto gr=G.groups();
    for(auto v:gr)C.emplace_back(sz(v));
  }
  
  sort(all(C));
  
  //L=1     L=2        L=3          L=4        L=5
  // 01     022        0233         02444      024555
  // 0      04         035          0366       03677
  //        0          04           048        0479
  //                   0            04         048
  //                                0          04
  //                                           0
  
  //f(i,j,L)  =  min(L,2i)+min(L-L%2,2i,2j,(i==jのときはi=j=L/2以外なら2i-1))
  // rep(L,1,6){
  //   cout<<"L="<<L<<endl;
  //   rep(j,0,L+1){rep(i,0,L-j+1)cout<<min(L,2*i)+min({L-L%2,2*i,2*j,(i==j&&2*i!=L&&i?2*i-1:L)})<<" ";cout<<endl;}
  // }
  
  vl E,O;
  for(auto c:C)(c%2?O:E).emplace_back(c);
  
  reverse(all(O));
  vl AE(sz(E)+1),AO(sz(O)+1),BO(sz(O)+1);
  rep(i,0,sz(E))AE[i+1]=AE[i]+E[i];
  rep(i,0,sz(O))AO[i+1]=AO[i]+O[i];
  rep(i,0,sz(O))BO[i+1]=BO[i]+O[i]-1;
  
  bitset<400000>B;
  B[0]=1;
  for(auto e:E)B|=B<<e;
  
  //cout<<C<<endl;
  
  ll zero=count(all(O),1);
  
  ll Q;cin>>Q;
  while(Q--){
    ll a,b,c;cin>>a>>b>>c;
    if(a==b&&B[a*2]){cout<<4*a<<endl;continue;}
    ll t=ub(AE,min(a,b)*2);
    ll ans=2*AE[t-1];
    a-=AE[t-1]/2;b-=AE[t-1]/2;
    if(t==sz(AE)){
      ll u=ub(BO,2*a);
      if(u==sz(BO)){
        chmin(a,BO.back()/2+sz(O));
        ans+=BO.back()+(a-BO.back()/2);
        ll bb=max(sz(O)-a+BO.back()/2-zero,0ll);
        ll two=BO.back()/2-bb;
        ll one=2*bb;
        if(b<=two)ans+=2*b;
        else ans+=2*two+min(one,b-two);
      }
      else{
        if(BO[u-1]==2*a)u--;
        ans+=2*a;
        ll two=a-u;
        ll one=2*u;
        if(b<=two)ans+=2*b;
        else ans+=2*two+min(one,b-two);
      }
    }
    else if(a<E[t-1]/2){
      ans+=2*a+min(2*b,(a==b&&a?2*a-1:2*a));
    }
    else{
      ans+=E[t-1]+2*b;a-=E[t-1]/2;
      ll rest=AE.back()-AE[t]+AO.back()-sz(O);
      if(rest>=2*a)ans+=2*a;
      else ans+=rest+min((ll)sz(O),a-rest/2);
    }
    cout<<ans<<endl;
  }
  return 0;
}

Submission Info

Judge Result