Submission #36199618

---

Source Code Expand

#include <bits/stdc++.h>
namespace // to fold that junk code
{
#define filein(x) {freopen(x".in", "r", stdin);}
#define file(x) {freopen(x".in", "r", stdin); freopen(x".out", "w", stdout);}
#define files(x) {freopen(x".in", "r", stdin); freopen(x".ans", "w", stdout);}
#define mem(x, a) memset(x, a, sizeof x);
#define cls(x) mem(x, 0)
using namespace std;
#define cT const T&
template<typename T>
inline T chkmin(T& x, cT y){if (x > y) x = y; return x;}
template<typename T>
inline T chkmax(T& x, cT y){if (x < y) x = y; return x;}
template <typename T>
inline bool inrange(cT x, cT l, cT r){return (l <= x) && (x <= r);}
template <typename T>
inline bool inrange(cT l, cT r, cT L, cT R){return (L <= l) && (r <= R);}
template <typename T>
inline bool separate(cT l, cT r, cT L, cT R){return (R < l) || (L > r);}
template <typename T>
inline T sqr(cT _){return _ * _;}
template <typename T>
inline T read(){T x; cin >> x; return x;}
template <typename T1, typename T2>
inline pair<T1, T2> read(){T1 x; T2 y; cin >> x >> y; return make_pair(x, y);}
template <typename T>
inline void clear(T& q){typename remove_reference<decltype(q)> :: type _; swap(q, _);} // remove_reference_t is since C++14
#undef cT
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
template <typename T>
using pr = pair<T, T>;
template <typename T>
using maxheap = priority_queue<T>;
template <typename T>
using minheap = priority_queue<T, vector<T>, greater<T>>;
template <typename T1, typename T2 = unsigned>
using umap = unordered_map<T1, T2>;
template <typename T1, typename T2 = unsigned>
using uset = unordered_set<T1, T2>;
typedef pr<int> pii;
typedef pr<ll> pll;
typedef pr<db> pdd;
typedef complex<double> cp;
typedef vector<int> vi;
inline void YN(bool x){puts(x ? "Yes" : "No");}
}
const int N = 222222, base1 = 1331, base2 = 131, P = 1e9 + 87;
int n, p, q, a[N], x[N], y[N], pb1[N], pb2[N], dist[N];
inline void initHash(int n)
{
	pb1[0] = pb2[0] = 1;
	for (int i=1; i<=n; i++) pb1[i] = 1ll * pb1[i-1] * base1 % P;
	for (int i=1; i<=n; i++) pb2[i] = 1ll * pb2[i-1] * base2 % P;
}
struct Hasher
{
	int ph1[N], ph2[N];
	template <typename _Iter>
	inline void init(_Iter beg, _Iter end)
	{
		ph1[1] = ph2[1] = beg[0]; int n = end - beg;
		for (int i=1; i<n; i++) ph1[i+1] = (1ll * ph1[i] * base1 % P + beg[i]) % P;
		for (int i=1; i<n; i++) ph2[i+1] = (1ll * ph2[i] * base2 % P + beg[i]) % P;
	}
	pii hash(int l, int r){return make_pair((ph1[r] - 1ll * ph1[l-1] * pb1[r-l+1] % P + P) % P, (ph2[r] - 1ll * ph2[l-1] * pb2[r-l+1] % P + P) % P);}
}A, B;
inline bool check(int len)
{
	set<pii> S;
	for (int i=1; i<=p-len+1; i++) S.insert(A.hash(i, i+len-1));
	for (int i=1; i<=q-len+1; i++)
		if (S.find(B.hash(i, i+len-1)) != S.end()) return true;
	return false;
}
vector<int> g[N];
inline void addedge(int u, int v){g[u].emplace_back(v);}
inline void ade(int u, int v){addedge(u, v); addedge(v, u);}
inline int bfs()
{
	memset(dist, 0x3f, sizeof dist);
	queue<int> Q;
	for (int i=1; i<=p; i++){dist[x[i]] = 0; Q.push(x[i]);}
	for (int i=2; i<=n; i++) ade(a[i], a[i-1]);
	while (!Q.empty())
	{
		int u = Q.front(); Q.pop();
		for (int v : g[u])
			if (dist[v] > dist[u] + 1){dist[v] = dist[u] + 1; Q.push(v);}
	}
	int ans = dist[0];
	for (int i=1; i<=q; i++) chkmin(ans, dist[y[i]]);
	return p + q + 2 * ans - 2;
}
int main()
{
	scanf("%d", &n); initHash(n);
	for (int i=1; i<=n; i++) scanf("%d", a+i);
	scanf("%d", &p);
	for (int i=1; i<=p; i++) scanf("%d", x+i);
	scanf("%d", &q);
	for (int i=1; i<=q; i++) scanf("%d", y+i);
	A.init(x+1, x+1+p); B.init(y+1, y+1+q);
	int l = 1, r = min(p, q);
	while (l <= r)
	{
		int mid = (l + r) >> 1;
		if (check(mid)) l = mid + 1;
		else r = mid - 1;
	}
	int lcs = l - 1;
	if (lcs) printf("%d\n", p + q - 2 * lcs);
	else printf("%d\n", bfs());
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:100:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  100 |  scanf("%d", &n); initHash(n);
      |  ~~~~~^~~~~~~~~~
./Main.cpp:101:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  101 |  for (int i=1; i<=n; i++) scanf("%d", a+i);
      |                           ~~~~~^~~~~~~~~~~
./Main.cpp:102:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  102 |  scanf("%d", &p);
      |  ~~~~~^~~~~~~~~~
./Main.cpp:103:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  103 |  for (int i=1; i<=p; i++) scanf("%d", x+i);
      |                           ~~~~~^~~~~~~~~~~
./Main.cpp:104:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  104 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
./Main.cpp:105:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  105 |  for (int i=1; i<=q; i++) scanf("%d", y+i);
      |                           ~~~~~^~~~~~~~~~~

Judge Result