Submission #602537

#	Time	Username	Problem	Language	Result	Execution time	Memory
602537		Tigryonochekk	Jail (JOI22_jail)	C++17	0 / 100	4 ms	3156 KiB

jail

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <string>
using namespace std;
#define ll long long
#define pii pair<int, int>
const int N = 1.2e5 + 2, lgN = 17;

int n;
int ln;
vector<int> g[N];
int p[N];
int tin[N], tout[N];
int timer;
int d[N][lgN];

int m;
int b[N], w[N];

void cleaning() {
	for (int i = 1; i <= n; i++) {
		g[i].clear();
	}
	fill(p + 1, p + n + 1, 0);
	fill(tin, tin + n + 1, 0);
	fill(tout, tout + n + 1, 0);
	timer = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < ln; j++) {
			d[i][j] = 0;
		}
	}
}

void dfs(int v) {
	tin[v] = timer++;
	for (int to : g[v]) {
		if (p[v] == to) continue;
		p[to] = v;
		d[to][0] = v;
		for (int i = 1; i < ln; i++) {
			d[to][i] = d[d[to][i - 1]][i - 1];
		}
		dfs(to);
	}
	tout[v] = timer++;
}

bool check(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b) {
	if (check(a, b)) return a;
	if (check(b, a)) return b;
	for (int i = ln - 1; i >= 0; i--) {
		if (!check(d[a][i], b))
			a = d[a][i];
	}
	return p[a];
}

void solve() {
	cin >> n;
	ln = log2(n) + 1;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	cin >> m;
	for (int i = 1; i <= m; i++) {
		cin >> b[i] >> w[i];
	}
	p[1] = 1;
	for (int i = 0; i < ln; i++) {
		d[1][i] = 1;
	}
	dfs(1);
	if(lca(b[1], w[1]) != lca(b[2], w[2]))
		cout << "Yes\n";
	else {
		if ((check(b[1], w[2]) && check(b[2], w[1])) || (check(w[2], b[1]) && check(w[1], b[2])))
			cout << "No\n";
		else
			cout << "Yes\n";
	}
	cleaning();
}

int main() {
	int t = 1;
	cin >> t;
	while (t--) 
		solve();
	return 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