Submission #666188

#	Time	Username	Problem	Language	Result	Execution time	Memory
666188		Kahou	Jail (JOI22_jail)	C++14	61 / 100	5066 ms	30400 KiB

jail

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mk make_pair
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 1.5e5 + 50;
int n, m, par[20][N], h[N], st[N], ft[N], tim;
int s[N], t[N];
int d[N];
vector<int> adj[N], adj2[N];
queue<int> q;

void dfs(int u, int p) {
	h[u] = h[p]+1;
	par[0][u] = p;
	st[u] = ++tim;
	for (int v:adj[u]) {
		if (v == p) continue;
		dfs(v, u);
	}
	ft[u] = tim;
}
int Par(int u, int x) {
	for (int k = 0; k < 20; k++) {
		if (x>>k&1) u = par[k][u];
	}
	return u;
}
int LCA(int u, int v) {
	if (h[u] < h[v]) swap(u, v);
	u = Par(u, h[u]-h[v]);
	for (int k = 19; k >= 0; k--) {
		if (par[k][u] != par[k][v]) u = par[k][u], v = par[k][v];
	}
	if (u == v) return u;
	return par[0][u];
}
bool issub(int u, int v) {
	return st[u] <= st[v] && st[v] <= ft[u];
}
void solve() {
	tim = 0;
	for (int u = 1; u <= n; u++) {
		adj[u].clear();
	}
	for (int u = 1; u <= m; u++) {
		adj2[u].clear();
		d[u] =0;
	}
	cin >> n;
	for (int i = 1; i <= n-1; i++) {
		int u,v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dfs(1, 0);
	for (int k = 1; k < 20; k++) {
		for (int u = 1; u <= n; u++) {
			par[k][u] = par[k-1][par[k-1][u]];
		}
	}
	cin >> m;
	for (int i = 1; i <= m; i++) {
		cin >> s[i] >> t[i];
	}
	for (int u = 1; u <= m; u++) {
		for (int v = 1; v <= m; v++) {
			if (u == v) continue;
			int r = LCA(s[u], t[u]);
			if (issub(r, s[v]) && (issub(s[v], s[u]) || issub(s[v], t[u]))) {
				d[u]++;
				adj2[v].push_back(u);
			}
			if (issub(r, t[v]) && (issub(t[v], s[u]) || issub(t[v], t[u]))) {
				d[v]++;
				adj2[u].push_back(v);
			}
		}
	}
	for (int u = 1; u <= m; u++) {
		if (!d[u]) q.push(u);
	}
	while (q.size()) {
		int u =q.front();
		q.pop();
		for (int v:adj2[u]) {
			d[v]--;
			if (!d[v]) q.push(v);
		}
	}
	bool flg = 1;
	for (int u = 1; u <= m; u++) {
		flg = flg&&(!d[u]);
	}
	cout << (flg? "Yes":"No") << endl;
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int tc;
	cin >> tc;
	while(tc--)
	solve();
	return 0;
}

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