提出 #35803366

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN=2e5+10,LIM=2e5,base=19260817,INF=1e9;
int n,a[MAXN];
int x,y,p[MAXN],q[MAXN];
int lcs;
ull pw[MAXN];
ull ha[MAXN],hp[MAXN],hq[MAXN];
int dis[MAXN];
queue<int>Q;
vector<int>e[MAXN];
ull qry(ull* h,int l,int r){
    return h[r]-h[l-1]*pw[r-l+1];
}
set<ull>S;
int check(int mid){
    S.clear();
    rep(i,mid,x)S.insert( qry(hp,i-mid+1,i) );
    rep(i,mid,y)if(S.find( qry(hq,i-mid+1,i) )!=S.end())return 1;
    return 0;
}
int main(){
    pw[0]=1;rep(i,1,LIM)pw[i]=pw[i-1]*base;
    //
    cin>>n;
    rep(i,1,n)cin>>a[i];
    cin>>x;rep(i,1,x)cin>>p[i];
    cin>>y;rep(i,1,y)cin>>q[i];
    //
    rep(i,1,n)ha[i]=ha[i-1]*base+a[i];
    rep(i,1,x)hp[i]=hp[i-1]*base+p[i];
    rep(i,1,y)hq[i]=hq[i-1]*base+q[i];
    //
    int L=1,R=min(x,y);
    while(L<=R){
        int mid=(L+R)>>1;
        if(check(mid)){
            lcs=mid;
            L=mid+1;
        }else{
            R=mid-1;
        }
    }
    if(lcs)cout<<x+y-2*lcs;
    else{
        rep(i,1,n)dis[i]=INF;
        rep(i,1,x)dis[p[i]]=0,Q.push(p[i]);
        rep(i,1,n-1)e[a[i]].push_back(a[i+1]),e[a[i+1]].push_back(a[i]);
        while(Q.size()){
            int u=Q.front();Q.pop();
            for(auto v:e[u])if(dis[v]>dis[u]+1){
                dis[v]=dis[u]+1;
                Q.push(v);
            }
        }
        int d=INF;
        rep(i,1,y)d=min(d,dis[q[i]]);
        cout<<x+y+2*(d-1);
    }
    return 0;
}

提出情報

ジャッジ結果