oj.uz

답안 #630002

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
630002 2022-08-15T14:01:28 Z flappybird Jail (JOI22_jail) C++17
0 / 100
 14 ms 5332 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 101010
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
vector<int> adj[MAX];
vector<int> graph[MAX];
int S[MAX];
int T[MAX];
int deg[MAX];
bool chk(int x, int ban, int e, int p = 0) {
	if (x == ban) return false;
	if (x == e) return true;
	for (auto v : adj[x]) {
		if (v == p) continue;
		if (v == ban) continue;
		if (chk(v, ban, e, x)) return true;
	}
	return false;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int Q;
	cin >> Q;
	while (Q--) {
		int N;
		cin >> N;
		int i, a, b;
		for (i = 1; i <= N; i++) adj[i].clear();
		for (i = 1; i < N; i++) cin >> a >> b, adj[a].push_back(b), adj[b].push_back(a);
		int M;
		cin >> M;
		for (i = 1; i <= M; i++) cin >> S[i] >> T[i], deg[i] = 0, graph[i].clear();
		int j;
		for (i = 1; i <= M; i++) {
			for (j = 1; j <= M; j++) {
				if (i == j) continue;
				int a, b, c;
				a = S[i];
				b = T[i];
				c = T[j];
				if (!chk(a, c, b)) {
					graph[i].push_back(j);
					deg[j]++;
				}
			}
		}
		int cnt = 0;
		queue<int> q;
		for (i = 1; i <= M; i++) if (!deg[i]) q.push(i);
		while (q.size()) {
			int t = q.front();
			cnt++;
			q.pop();
			for (auto v : graph[t]) {
				deg[v]--;
				if (!deg[v]) q.push(v);
			}
		}
		if (cnt == M) cout << "Yes" << ln;
		else cout << "No" << ln;
	}
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 28.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 11.0

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

Subtask #7
0 / 23.0

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