Submission #588495

#	Time	Username	Problem	Language	Result	Execution time	Memory
588495		valerikk	Jail (JOI22_jail)	C++17	49 / 100	534 ms	577256 KiB

jail

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <cmath>
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <iomanip>

using namespace std;

#define all(a) (a).begin(), (a).end()
#define sz(a) ((int)(a).size())
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define y1 y1111

using ll = long long;
using ld = long double;

const int N = 1.2e5 + 7;
const int M = 1e7;

int n, m;
vector<int> g[N];
int s[N], t[N];
int rs[N], rt[N];
int sz[N];
bool used[N];
int f[N];
vector<int> g1[M];
int id[N];
int par[N];
bool ans;
int used1[N];

int dfs(int u, int p) {
	sz[u] = 1;
	for (int v : g[u]) {
		if (!used[v] && v != p) {
			sz[u] += dfs(v, u);
		}
	}
	return sz[u];
}

int centroid(int u, int p, int n1) {
	for (int v : g[u]) {
		if (!used[v] && v != p && 2 * sz[v] > n1) {
			return centroid(v, u, n1);
		}
	}
	return u;
}

void dfs1(int u, int p) {
	if (p == -1) f[u] = u;
	par[u] = p;
	id[u] = m;
	g1[id[u]].clear();
	g1[id[u] + 1].clear();
	m += 2;
	if (p != -1) {
		if (rs[u] != -1) g1[id[u]].pb(rs[u]);
		if (rt[u] != -1) g1[rt[u]].pb(id[u] + 1);
		g1[id[u]].pb(id[p]);
		g1[id[p] + 1].pb(id[u] + 1);
	}
	for (int v : g[u]) {
		if (!used[v] && v != p) {
			f[v] = p == -1 ? v : f[u];
			dfs1(v, u);
		}
	}
}

void dfs2(int u) {
	used1[u] = 1;
	for (int v : g1[u]) {
		if (used1[v] == 1) ans = 0;
		if (!used1[v]) dfs2(v);
	}
	used1[u] = 2;
}

void go(int u, const vector<int> &who) {
	dfs1(u, -1);
	map<int, vector<int>> who1;
	for (int i : who) {
		if (f[s[i]] != f[t[i]]) {
			if (s[i] != u) g1[i].pb(id[par[s[i]]]);
			g1[i].pb(id[t[i]]);
			if (t[i] != u) g1[id[par[t[i]]] + 1].pb(i);
			g1[id[s[i]] + 1].pb(i);
			if (rs[u] != -1 && u != s[i]) {
				g1[i].pb(rs[u]);
			}
			if (rt[u] != -1 && u != t[i]) {
				g1[rt[u]].pb(i);
			}
		} else {
			who1[f[s[i]]].pb(i);
		}
	}
	used[u] = 1;
	for (int v : g[u]) {
		if (!used[v]) {
			dfs(v, -1);
			int c = centroid(v, -1, sz[v]);
			go(c, who1[v]);
		}
	}
}

void solve() {
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		g[i].clear();
	}
	for (int i = 0; i < n - 1; ++i) {
		int a, b;
		cin >> a >> b;
		g[a].pb(b);
		g[b].pb(a);
	}
	cin >> m;
	for (int i = 1; i <= n; ++i) {
		rs[i] = -1;
		rt[i] = -1;
	}
	for (int i = 0; i < m; ++i) {
		cin >> s[i] >> t[i];
		rs[s[i]] = i;
		rt[t[i]] = i;
		g1[i].clear();
	}
	for (int i = 1; i <= n; ++i) {
		used[i] = 0;
	}
	vector<int> who;
	for (int i = 0; i < m; ++i) {
		if (s[i] != t[i]) {
			who.pb(i);
		}
	}
	dfs(1, -1);
	int c = centroid(1, -1, n);
	go(c, who);
	ans = 1;
	for (int i = 0; i < m; ++i) {
		used1[i] = 0;
	}
	for (int i = 0; i < m; ++i) {
		if (!used1[i]) dfs2(i);
	}
	cout << (ans ? "Yes" : "No") << endl;
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int q;
	cin >> q;
	while (q--) {
		solve();
	}
	return 0;	
}

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