提出 #49162531

---

ソースコード 拡げる

/*
Author: cnyz
世界があたしを拒んでも今 愛の唄 歌わせてくれないかな
*/
#include<bits/stdc++.h>
using namespace std;

using db=double;
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
using ull=unsigned long long;

#define fi first
#define se second
#define gc getchar
#define pb emplace_back
#define mkp make_pair
#define push emplace
#define sz(a) (int)a.size()
#define all(p) p.begin(),p.end()
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define ppc(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)

bool Mbe;

void chkmax(int &x,int y) {if(x<y) x=y;}
void chkmin(int &x,int y) {if(x>y) x=y;}
void chkmax(ll &x,ll y) {if(x<y) x=y;}
void chkmin(ll &x,ll y) {if(x>y) x=y;}
int read() { int x; cin>>x; return x; }

const int N=2e5+5;
int n,p,q,a[N],b[N],c[N];
struct Hash {
    int pw[N],s[N],p;
    void init(int base,int mod,int *a,int n) {
        p=mod,pw[0]=1;
        FOR(i,1,n) s[i]=(1ll*s[i-1]*base%p+a[i]%p),pw[i]=1ll*pw[i-1]*base%p;
    }
    int get(int l,int r) {
        return (s[r]-1ll*s[l-1]*pw[r-l+1]%p+p)%p;
    }
} p1,p2,q2,q1;
map<pii,int> mp;
bool chk(int x) {
    mp.clear();
    FOR(i,1,p-x+1) mp[mkp(p1.get(i,i+x-1),p2.get(i,i+x-1))]=1;
    FOR(i,1,q-x+1) if(mp.find(mkp(q1.get(i,i+x-1),q2.get(i,i+x-1)))!=mp.end()) return 1;
    return 0;
}
vector<pii> G[N];
int dis[N];
int bfs(int u) {
    FOR(i,1,n+2) dis[i]=n*10;
    dis[u]=0; deque<int> q; q.push_back(u);
    while(sz(q)) {
        int u=q.front(); q.pop_front();
        for(auto [v,d]:G[u]) if(dis[v]>dis[u]+d) {
            dis[v]=dis[u]+d;
            if(d==0) q.push_front(v);
            else q.push_back(v);
        }
    }
    return dis[n+2];
}
int calc() {
    int S=n+1,T=n+2;
    FOR(i,1,p) G[S].pb(mkp(b[i],0));
    FOR(i,1,q) G[c[i]].pb(mkp(T,0));
    FOR(i,1,n-1) G[a[i]].pb(mkp(a[i+1],1)),G[a[i+1]].pb(mkp(a[i],1));
    int d=bfs(S);
    return p+q+d*2-2;
}
void solve() {
    n=read(); FOR(i,1,n) a[i]=read();
    p=read(); FOR(i,1,p) b[i]=read();
    q=read(); FOR(i,1,q) c[i]=read();
    p1.init(19491001,1e9+7,b,p);
    p2.init(19491001,1e9+9,b,p);
    q1.init(19491001,1e9+7,c,q);
    q2.init(19491001,1e9+9,c,q);
    int l=1,r=min(p,q),s=0;
    while(l<=r) {
        int mid=(l+r)>>1;
        if(chk(mid)) s=mid,l=mid+1;
        else r=mid-1;
    }
    if(s) cout<<p+q-2*s<<"\n";
    else cout<<calc()<<"\n";
}

bool Med;
int main() {
    ios::sync_with_stdio(false),cin.tie(0);
    // fprintf(stderr, "%.3lf MB\n", (&Med - &Mbe) / 1048576.0);
    int T=1;
    while(T--) solve();
    // fprintf(stderr, "%d ms\n", int(1e3 * clock() / CLOCKS_PER_SEC));
}

提出情報

ジャッジ結果