oj.uz

Submission #788248

# Submission time Handle Problem Language Result Execution time Memory
788248 2023-07-20T03:36:27 Z iee Jail (JOI22_jail) C++17
0 / 100
 47 ms 57044 KB 
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1200005;
int n, m;
int st[N], to[N];
vector<int> tr[N], e[N];
int bh[N];
int ma;
int dfn[N], faz[N], dep[N], siz[N], son[N], top[N];
int dfn_now;
void dfs1(int u, int fa) {
	faz[u] = fa;
	dep[u] = dep[fa] + 1;
	siz[u] = 1;
	for (int v : tr[u]) {
		if (v == fa) {
			continue;
		}
		dfs1(v, u);
		siz[u] += siz[v];
		if (siz[v] > siz[son[u]]) {
			son[u] = v;
		}
	}
}
void dfs2(int u, int tp) {
	top[u] = tp;
	dfn[u] = ++dfn_now;
	if (son[u]) {
		dfs2(son[u], tp);
	}
	for (int v : tr[u]) {
		if (v == faz[u] || v == son[u]) {
			continue;
		}
		dfs2(v, v);
	}
}
vector<int> bb;
void cqj(int u, int l, int r, int ql, int qr) {
	if (l >= ql && r <= qr) {
		bb.push_back(u);
		return;
	}
	const int mid = (l + r) >> 1;
	if (ql <= mid) cqj(u << 1, l, mid, ql, qr);
	if (qr > mid) cqj(u << 1 | 1, mid + 1, r, ql, qr);
}
void jqj(int di, int L, int R) {
	cqj(1, 1, n, L, R);
	e[di].insert(e[di].end(), bb.begin(), bb.end());
	bb.clear();
}
void jia(int di, int L, int R, int zho) {
	if (R < zho || L > zho) {
		jqj(di, L, R);
	} else {
		if (L < zho) jqj(di, L, zho - 1);
		if (zho < R) jqj(di, zho + 1, R);
	}
}
void jb(int di, int u, int v) {
	int zho = dfn[v];
	while (top[u] != top[v]) {
		if (dep[top[u]] < dep[top[v]]) {
			swap(u, v);
		}
		jia(di, dfn[top[u]], dfn[u], zho);
		u = faz[top[u]];
	}
	if (dep[u] < dep[v]) {
		swap(u, v);
	}
	jia(di, dfn[v], dfn[u], zho);
}
void jqj2(int l, int r, int di) {
	cqj(1, 1, n, l, r);
	for (auto i : bb) {
		e[i + ma].push_back(di);
	}
	bb.clear();
}
void jia2(int L, int R, int di, int zho) {
	if (R < zho || L > zho) {
		jqj2(L, R, di);
	} else {
		if (L < zho) jqj2(L, zho - 1, di);
		if (zho < R) jqj2(zho + 1, R, di);
	}
}
void jb2(int u, int v, int di) {
	int zho = dfn[u];
	while (top[u] != top[v]) {
		if (dep[top[u]] < dep[top[v]]) {
			swap(u, v);
		}
		jia2(dfn[top[u]], dfn[u], di, zho);
		u = faz[top[u]];
	}
	if (dep[u] < dep[v]) {
		swap(u, v);
	}
	jia2(dfn[v], dfn[u], di, zho);
}
void xj(int u, int l, int r) {
	if (u != 1) {
		e[u / 2].push_back(u);
	}
	if (l == r) {
		bh[l] = u;
		return;
	}
	const int mid = (l + r) >> 1;
	xj(u << 1, l, mid);
	xj(u << 1 | 1, mid + 1, r);
}
void xj2(int u, int l, int r) {
	if (u != 1) {
		e[u + ma].push_back(u / 2 + ma);
	}
	if (l == r) {
		bh[l] = u;
		return;
	}
	const int mid = (l + r) >> 1;
	xj2(u << 1, l, mid);
	xj2(u << 1 | 1, mid + 1, r);
}
bool vis[N], ins[N];
bool dag() {
	bool flag = 1;
	function<void(int)> dfs = [&](int u) {
		if (ins[u]) {
			flag = 0;
			return;
		}
		if (vis[u]) {
			return;
		}
		ins[u] = 1;
		vis[u] = 1;
		for (int v : e[u]) {
			dfs(v);
			if (!flag) {
				break;
			}
		}
		ins[u] = 0;
	};
	for (int i = 1; i <= ma * 2 + m; i++) {
		dfs(i);
	}
	return flag;
}
void solve() {
	cin >> n;
	for (int i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		tr[u].push_back(v);
		tr[v].push_back(u);
	}
	cin >> m;
	for (int i = 1; i <= m; i++) {
		cin >> st[i] >> to[i];
	}
	dfs1(1, 0), dfs2(1, 1);
	ma = n * 4 + 10;
	xj(1, 1, n);
	for (int u = 1; u <= m; u++) {
		jb(u + ma * 2, st[u], to[u]);
	}
	for (int v = 1; v <= m; v++) {
		e[bh[dfn[to[v]]]].push_back(v + ma * 2);
	}
	for (int u = 1; u <= m; u++) {
		e[u + ma * 2].push_back(bh[dfn[st[u]]]);
	}
	for (int v = 1; v <= m; v++) {
		jb2(st[v], to[v], v + ma * 2);
	}
	xj2(1, 1, n);
	if (dag()) cout << "Yes" << "\n";
	else cout << "No" << "\n";
}
void clear() {
	for (int i = 1; i <= ma * 2 + m; i++) {
		st[i] = to[i] = bh[i] = dfn[i] = faz[i] = dep[i] = siz[i] = son[i] = top[i] = vis[i] = ins[i] = 0;
		tr[i].clear(), e[i].clear();
	}
	n = m = ma = dfn_now = 0;
}
int main() {
	int T;
	cin >> T;
	while (T--) {
		solve();
		clear();
	}
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 56660 KB Output is correct
2 Correct 26 ms 56716 KB Output is correct
3 Correct 26 ms 56684 KB Output is correct
4 Incorrect 47 ms 57044 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 56756 KB Output is correct
2 Correct 24 ms 56660 KB Output is correct
3 Incorrect 27 ms 56880 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 56756 KB Output is correct
2 Correct 24 ms 56660 KB Output is correct
3 Incorrect 27 ms 56880 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 56756 KB Output is correct
2 Correct 24 ms 56660 KB Output is correct
3 Incorrect 27 ms 56880 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 56756 KB Output is correct
2 Correct 24 ms 56660 KB Output is correct
3 Incorrect 27 ms 56880 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 56680 KB Output is correct
2 Correct 23 ms 56684 KB Output is correct
3 Correct 24 ms 56644 KB Output is correct
4 Correct 26 ms 56756 KB Output is correct
5 Incorrect 46 ms 56800 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 56660 KB Output is correct
2 Correct 26 ms 56716 KB Output is correct
3 Correct 26 ms 56684 KB Output is correct
4 Incorrect 47 ms 57044 KB Output isn't correct
5 Halted 0 ms 0 KB -