oj.uz

답안 #787834

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
787834 2023-07-19T13:11:12 Z iee Jail (JOI22_jail) C++17
0 / 100
 297 ms 443280 KB 
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 900005;
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];
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;
	static int dfn_now = 0;
	dfn[++dfn_now] = u;
	if (son[u]) {
		dfs2(son[u], tp);
		return;
	}
	for (int v : tr[u]) {
		if (v == faz[u] || v == son[u]) {
			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, mid + 1, r, ql, qr);
}
void jjq(int di) {
	e[di].insert(tr[di].end(), bb.begin(), bb.end());
	bb.clear();
}
void jb(int di, int u, int v) {
	while (top[u] != top[v]) {
		if (dep[top[u]] < dep[top[v]]) {
			swap(u, v);
		}
		cqj(1, 1, n, dfn[top[u]], dfn[u]), jjq(di);
		u = faz[top[u]];
	}
	if (dep[u] < dep[v]) {
		swap(u, v);
	}
	cqj(1, 1, n, dfn[v], dfn[u]), jjq(di);
}
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);
}
int tpx[N], rd[N];
bool dag() {
	for (int i = 1; i <= ma + n; i++) {
		for (int j : e[i]) {
			rd[j]++;
		}
	}
	queue<int> q;
	for (int i = 1; i <= ma + n; i++) {
		if (rd[i] == 0) {
			q.push(i);
		}
	}
	int shu = 0;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		tpx[u] = ++shu;
		for (int v : e[u]) {
			if (!--rd[v]) {
				q.push(v);
			}
		}
	}
	for (int i = 1; i <= ma + n; i++) {
		for (int j : e[i]) {
			if (tpx[j] <= tpx[i]) {
				return 0;
			}
		}
	}
	return 1;
}
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;
	for (int u = 1; u <= m; u++) {
		jb(u + ma, st[u], to[u]);
	}
	xj(1, 1, n);
	for (int v = 1; v <= m; v++) {
		e[bh[to[v]]].push_back(v + ma);
	}
	if (dag()) cout << "Yes" << "\n";
	else cout << "No" << "\n";
}
void clear() {
	for (int i = 1; i <= ma + n; i++) {
		st[i] = to[i] = bh[i] = dfn[i] = faz[i] = dep[i] = siz[i] = son[i] = top[i] = tpx[i] = rd[i] = 0;
	}
	n = m = ma = 0;
}
int main() {
	int T;
	cin >> T;
	while (T--) {
		solve();
		clear();
	}
	return 0;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 297 ms 443280 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 278 ms 443220 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 278 ms 443220 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 278 ms 443220 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 278 ms 443220 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 281 ms 443232 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 297 ms 443280 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -