Submission #580632

#	Time	Username	Problem	Language	Result	Execution time	Memory
580632		AriaH	Jail (JOI22_jail)	C++17	0 / 100	5034 ms	1048576 KiB

jail

/* Ignore Others Only Focus On Yourself! */
/* Im the Best! */
 
#pragma GCC optimize("O3")
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
 
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define Mp make_pair
#define point complex
#define endl '\n'
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
#define mashtali return cout << "Hello, World!", 0;
 
const int N = 2e5 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const double pi = acos(-1);
const ld eps = 1e-18;
const ld one = 1.;
 
ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }
 
mt19937 rng(time(nullptr));
 
int n, m, ts, ptr, St[N], Fi[N], node[N], sub[N], H[N], P[N], Hd[N], Hv[N], S[N], T[N], Start[N], End[N];

vector < int > G[N], adj[N << 3], adt[N << 3];

int mark[N << 3];

void add(int v, int u, int tp)
{
	if(!v || !u) return;
	if(tp) swap(v, u);
	adj[v].push_back(u);
	adt[u].push_back(v);
}

struct segment
{
	int tp, seg[N << 2]; /// tp = 0 -> End, tp = 1 -> Start
	segment(int _tp)
	{
		tp = _tp;
	}
	void build(int v = 1, int tl = 1, int tr = n)
	{
		seg[v] = ++ts;
		if(tl == tr) /// you can optimize this part with just puting the node in the last layer of segment
		{
			int now = node[tl];
			if(tp == 0 && End[now])
			{
				add(seg[v], End[now], tp);
			}
			if(tp == 1 && Start[now])
			{
				add(seg[v], Start[now], tp);
			}
			return;
		}
		int mid = (tl + tr) >> 1;
		build(v << 1, tl, mid), build(v << 1 | 1, mid + 1, tr);

		add(seg[v], seg[v << 1], tp);
		add(seg[v], seg[v << 1 | 1], tp);
	}
	void upd(int l, int r, int x, int v = 1, int tl = 1, int tr = n)
	{
		if(l > tr || r < tl || l > r) return;
		if(l <= tl && tr <= r)
		{
			add(x, seg[v], tp);
			return;
		}
		int mid = (tl + tr) >> 1;
		upd(l, r, x, v << 1, tl, mid);
		upd(l, r, x, v << 1 | 1, mid + 1, tr);
	}
};

void dfs(int v)
{
	Hv[v] = 0;
	sub[v] = 1;
	H[v] = H[P[v]] + 1;
	for(auto u : G[v])
	{
		if(u == P[v]) continue;
		P[u] = v;
		dfs(u);
		if(sub[Hv[v]] < sub[u])
		{
			Hv[v] = u;
		}
		sub[v] += sub[u];
	}
}
 
void Hld(int v)
{
	St[v] = ++ptr;
	node[ptr] = v;
	if(Hv[v])
	{
		Hd[Hv[v]] = Hd[v];
		Hld(Hv[v]);
	}
	for(auto u : G[v])
	{
		if(u == P[v] || u == Hv[v]) continue;
		Hd[u] = u;
		Hld(u);
	}
	Fi[v] = ptr;
}

int cnt;

vector < int > top;

void DFS(int v)
{
	mark[v] = 1;
	for(auto u : adj[v])
	{
		if(mark[u])
		{
			continue;
		}
		DFS(u);
	}
	top.push_back(v);
}

void SFD(int v)
{
	mark[v] = 1;
	if(v <= m) cnt ++;
	for(auto u : adt[v])
	{
		if(mark[u]) continue;
		SFD(u);
	}
}

void solve()
{
	cin >> n;
	for(int i = 1; i < n; i ++)
	{
		int a, b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	dfs(1);
	Hld(Hd[1] = 1);
	cin >> m;
	ts = m;
	for(int i = 1; i <= m; i ++)
	{
		cin >> S[i] >> T[i];
		Start[S[i]] = i;
		End[T[i]] = i;
	}
	segment S0(0), S1(1);
	S0.build();
	S1.build();
	for(int i = 1; i <= m; i ++)
	{
		int v = S[i], u = T[i];
		while(Hd[v] != Hd[u])
		{
			if(H[Hd[v]] < H[Hd[u]]) swap(u, v);
			S0.upd(St[Hd[v]], St[v], i);
			S1.upd(St[Hd[v]], St[v], i);
			v = P[Hd[v]];
		}
		if(H[v] < H[u]) swap(u, v);
		S0.upd(St[u], St[v], i);
		S1.upd(St[u], St[v], i);
	}
	for(int i = 1; i <= m; i ++)
	{
		if(!mark[i])
		{
			DFS(i);
		}
	}
	for(int i = 0; i <= ts; i ++) mark[i] = 0;
	reverse(all(top));
	int ans = 1;
	for(auto v : top)
	{
		if(!mark[v])
		{
			cnt = 0;
			SFD(v);
			if(cnt > 1)
			{
				ans = 0;
				break;
			}
		}
	}
	if(!ans)
	{
		cout << "No\n";
	}
	else
	{
		cout << "Yes\n";
	}
	for(int i = 0; i <= ts; i ++) adj[i].clear(), adt[i].clear(), mark[i] = 0;
	for(int i = 0; i <= n; i ++) Start[i] = 0, End[i] = 0;
	top.clear();
	cnt = 0;
	ts = 0;
	ptr = 0;
}
 
int main()
{
	fast_io;
	int q = 1;
	cin >> q;
	while(q --)
	{
		solve();
	}
}

/* check corner case(n = 1?), watch for negetive index or overflow */

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23