Submission #609603

#	Time	Username	Problem	Language	Result	Execution time	Memory
609603		Tigryonochekk	Jail (JOI22_jail)	C++17	77 / 100	5096 ms	369576 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, M = N;

int n, ln;
vector<int> g[N];
int m;
int b[N], w[N];

pii sb[N], sw[N];

int p[N];
int tin[N], tout[N];
int timer;
int d[N][lgN];

set<int> pp[M];
int col[M];

int rb[N], rw[N]; // reverce bed and workplace

void LEVI() {
	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;
		}
	}
	for (int i = 1; i <= m; i++) {
		pp[i].clear();
	}
	fill(col, col + m + 1, 0);
	fill(rb, rb + n + 1, 0);
	fill(rw, rw + n + 1, 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));
}

int compare(int i, int j) { //0 - lriv, 1-skizb, 2-verj, 3-vochinch
	if (belong(b[i], w[i], b[j])) {
		if (belong(b[i], w[i], w[j])) {
			return 0;
		}
		else
			return 1;
	}
	else {
		if (belong(b[i], w[i], w[j]))
			return 2;
		else
			return 3;
	}
}

void edging(int i, int j) {
	if (j == i) return;
	int com = compare(i, j);
	if (com == 0) {
		pp[i].insert(j);
		pp[j].insert(i);
	}
	else if (com == 1) {
		pp[i].insert(j);
	}
	else if (com == 2) {
		pp[j].insert(i);
	}
}

bool dps(int v) {
	bool ret = 1;
	col[v] = 1;
	for (auto to : pp[v]) {
		if (col[to] == 2) continue;
		if (col[to] == 1) return 0;
		col[to] = 1;
		ret &= dps(to);
	}
	col[v] = 2;
	return ret;
}

void solve() {
	LEVI();
	cin >> n;
	ln = log2(n) + 1;
	bool flag = true;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		if (x != i || y != i + 1)
			flag = false;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	cin >> m;
	for (int i = 1; i <= m; i++) {
		cin >> b[i] >> w[i];
		rb[b[i]] = i;
		rw[w[i]] = i;
	}
	if (flag) {
		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\n";
				return;
			}
		}
		cout << "Yes\n";
	}
	else {
		p[1] = 1;
		for (int i = 0; i < ln; i++) {
			d[1][i] = 1;
		}
		dfs(1);
		for (int i = 1; i <= m; i++) {
			int l = lca(b[i], w[i]);
			for (int j = b[i]; j != l; j = p[j]) {
				if (rw[j]) {
					edging(i, rw[j]);
				}
				if (rb[j]) {
					edging(i, rb[j]);
				}
			}
			for (int j = w[i]; j != l; j = p[j]) {
				if (rw[j]) {
					edging(i, rw[j]);
				}
				if (rb[j]) {
					edging(i, rb[j]);
				}
			}
			if (rw[l]) {
				edging(i, rw[l]);
			}
			if (rb[l]) {
				edging(i, rb[l]);
			}
		}
		bool ans = 1;
		for (int i = 1; i <= m; i++) {
			if (col[i] == 0) {
				ans &= dps(i);
			}
		}
		//cout << "imbluedabudidabudaidabudidabudaidabudidabudai\n";
		if (ans)
			cout << "Yes\n";
		else
			cout << "No\n";
	}
}

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

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