제출 #602554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
602554		Tigryonochekk	Jail (JOI22_jail)	C++17	5 / 100	5075 ms	8212 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];

pii sb[N], sw[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];
}

bool belong(int a, int b, int c) {
	return check(lca(a, b), c) && (check(c, a) || check(c, b));
}

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];
	}
	if (m <= 2) {
		p[1] = 1;
		for (int i = 0; i < ln; i++) {
			d[1][i] = 1;
		}
		dfs(1);
		if (belong(b[1], w[1], b[2]) && belong(b[2], w[2], b[1]))
			cout << "No\n";
		else if (belong(b[1], w[1], w[2]) && belong(b[2], w[2], w[1]))
			cout << "No\n";
		else if (belong(b[1], w[1], w[2]) && belong(b[1], w[1], b[2]))
			cout << "No\n";
		else if (belong(b[2], w[2], w[1]) && belong(b[2], w[2], b[1]))
			cout << "No\n";
		else
			cout << "Yes\n";
		cleaning();
	}
	else {
		for (int i = 1; i <= m; i++) {
			sb[i] = pii(b[i], i);
			sw[i] = pii(w[i], i);
		}
		sort(sb + 1, sb + m + 1);
		sort(sw + 1, sw + m + 1);
		for (int i = 1; i <= m; i++) {
			if (sb[i].second != sw[i].second) {
				cout << "No" << endl;
				return;
			}
		}
		cout << "Yes" << endl;
	}
}

int main() {
	int t = 1;
	cin >> t;
	while (t--) 
		solve();
	return 0;
}

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