oj.uz

답안 #887629

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
887629 2023-12-14T21:34:18 Z TAhmed33 Jail (JOI22_jail) C++
0 / 100
 17 ms 6092 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 120025;
vector <int> adj[MAXN];
set <int> adj2[501];
int n, m;
int l[501], r[501], deg[501];
vector <int> dd[MAXN];
bool dfs (int pos, int par, int c) {
	if (pos == r[c]) {
		dd[pos].push_back(c);
		return 1;
	}
	bool f = 0;
	for (auto i : adj[pos]) {
		if (i != par) {
			f |= dfs(i, pos, c);
		}
	}
	if (f) dd[pos].push_back(c);
	return f;
}
void reset () {
	for (int i = 1; i <= n; i++) {
		adj[i].clear();
		dd[i].clear();
	}
}
int main () {
	int t = 1; cin >> t;
	while (t--) {
		cin >> n;
		reset();
		for (int i = 1; i < n; i++) {
			int a, b;
			cin >> a >> b;
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
		cin >> m;
		for (int i = 1; i <= m; i++) {
			deg[i] = 0; adj2[i].clear();
		}
		for (int i = 1; i <= m; i++) {
			cin >> l[i] >> r[i];
			dfs(l[i], -1, i);
		}
		for (int i = 1; i <= m; i++) {
			for (auto j : dd[r[i]]) {
				adj2[i].insert(j);
			}
			adj2[i].erase(i);
		}
		for (int i = 1; i <= m; i++) {
			for (auto j : adj2[i]) {
				deg[j]++;
			}
		}
		vector <int> d;
		queue <int> cur;
		for (int i = 1; i <= m; i++) {
			if (deg[i] == 0) {
				cur.push(i);
			}
		}
		while (!cur.empty()) {
			auto j = cur.front();
			cur.pop();
			d.push_back(j);
			for (auto z : adj2[j]) {
				deg[z]--;
				if (deg[z] == 0) cur.push(z);
			}
		}
		if ((int)d.size() != m) {
			cout << "No\n";
		} else {
			cout << "Yes\n";
		}
	}
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5980 KB Output is correct
2 Correct 2 ms 5996 KB Output is correct
3 Correct 3 ms 5980 KB Output is correct
4 Incorrect 17 ms 6092 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5980 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Incorrect 3 ms 5980 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5980 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Incorrect 3 ms 5980 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5980 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Incorrect 3 ms 5980 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5980 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Incorrect 3 ms 5980 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5980 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Incorrect 12 ms 5860 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 5980 KB Output is correct
2 Correct 2 ms 5996 KB Output is correct
3 Correct 3 ms 5980 KB Output is correct
4 Incorrect 17 ms 6092 KB Output isn't correct
5 Halted 0 ms 0 KB -