Submission #1135393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135393		NK_	Jail (JOI22_jail)	C++20	0 / 100	12 ms	328 KiB

jail

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())

template<class T> using V = vector<T>;
using vi = V<int>;

const int LG = 17;
void solve() {
	int N; cin >> N;

	V<vi> adj(N); for(int i = 0; i < N - 1; i++) {
		int u, v; cin >> u >> v; --u, --v;
		adj[u].pb(v);
		adj[v].pb(u);
	}

	V<vi> up(N, vi(LG)); vi dep(N);
	function<void(int, int)> gen = [&](int u, int p) {
		up[u][0] = p; for(int i = 1; i < LG; i++) up[u][i] = up[up[u][i-1]][i-1];

		for(auto& v : adj[u]) if (v != p) {
			dep[v] = dep[u] + 1;
			gen(v, u);
		}
	};

	gen(0, 0);

	auto jmp = [&](int u, int d) {
		for(int i = 0; i < LG; i++) if ((d >> i) & 1) u = up[u][i];
		return u;
	};

	auto lca = [&](int a, int b) {
		if (dep[a] < dep[b]) swap(a, b);

		a = jmp(a, dep[a] - dep[b]);

		if (a == b) return a;

		for(int i = LG - 1; i >= 0; i--) {
			if (up[a][i] != up[b][i]) {
				a = up[a][i];
				b = up[b][i];
			}
		}

		return up[a][0];
	};

	int M; cin >> M;

	vi S(N, -1), T(N, -1), L(M), A(M), B(M);
	for(int i = 0; i < M; i++) {
		int s, t; cin >> s >> t; --s, --t;
		S[s] = T[t] = i;
		A[i] = s, B[i] = t;
		L[i] = lca(s, t);
		// cout << A[i] << " " << B[i] << " -> " << L[i] << endl;
	}

	V<vi> ADJ(M); vi in(M);

	auto ae = [&](int u, int v) { 
		// cout << u << " ===> " << v << endl;
		ADJ[u].pb(v);
		in[v]++;
	};

	function<void(int, int, int, int)> dfs = [&](int u, int p, int s, int t) {
		// cout << u << " -> " << s << " " << t << endl;
		if (T[u] != -1) {
			int i = T[u];
			if (s != i && s != -1 && dep[s] >= dep[L[i]]) ae(s, i);
			if (t != i && t != -1 && dep[t] >= dep[L[i]]) ae(i, t);

			t = i;
		}

		if (S[u] != -1) {
			int i = S[u];
			if (s != i && s != -1 && dep[s] >= dep[L[i]]) ae(s, i);
			if (t != i && t != -1 && dep[t] >= dep[L[i]]) ae(i, t);

			s = i;
		}

		for(auto& v : adj[u]) if (v != p) {
			dfs(v, u, s, t);
		}
	};

	dfs(0, -1, -1, -1);

	vi q; for(int i = 0; i < M; i++) if (in[i] == 0) q.pb(i);	

	for(auto& u : q) {
		for(auto& v : ADJ[u]) {
			--in[v]; 
			if (in[v] == 0) q.pb(v);
		}
	}

	cout << (sz(q) == M ? "Yes" : "No") << nl;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	

	int T; cin >> T; while(T--) {
		solve();
	}


	exit(0-0);
}

• 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