Submission #630203

#	Time	Username	Problem	Language	Result	Execution time	Memory
630203		flappybird	Jail (JOI22_jail)	C++17	49 / 100	5081 ms	10068 KiB

jail

#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]++;
				}
			}
		}
		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 = S[j];
				if (!chk(a, c, b)) {
					graph[j].push_back(i);
					deg[i]++;
				}
			}
		}
		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
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23