제출 #560887

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
560887		8e7	Jail (JOI22_jail)	C++17	49 / 100	5048 ms	1048576 KiB

jail

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 120005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<int> adj[maxn], g[maxn];
set<int> path[maxn];
int anc[18][maxn], dep[maxn], deg[maxn];
pii ed[maxn];
void dfs(int n, int par, int d) {
	anc[0][n] = par;
	dep[n] = d;	
	for (int v:adj[n]) {
		if (v != par) {
			dfs(v, n, d + 1);
		}
	}
}
int main() {
	io
	int T;
	cin >> T;
	while (T--) {

		int n;
		cin >> n;
		for (int i = 1;i <= n;i++) {
			adj[i].clear();
			g[i].clear();
			path[i].clear();
			deg[i] = 0;
		}
		for (int i = 0;i < n - 1;i++) {
			int u,v;
			cin >> u >> v;
			adj[u].push_back(v);
			adj[v].push_back(u);
		}
		dfs(1, 0, 0);
		int m;
		cin >> m;
		auto addedge = [&] (int u, int v) {
			//debug("edge", u, v);
			g[u].push_back(v);
			deg[v]++;
		};
		for (int i = 1;i <= m;i++) {
			int u, v;
			cin >> u >> v;
			int tu = u, tv = v;	
			while (tu != tv) {
				if (dep[tu] < dep[tv]) swap(tu, tv);
				path[i].insert(tu);
				tu = anc[0][tu];
			}
			path[i].insert(tu);
			ed[i] = {u, v};
		}
		for (int i = 1;i <= m;i++) {
			for (int j = i+1;j <= m;j++) {
				if (path[i].find(ed[j].ff) != path[i].end()) addedge(j, i);
				if (path[i].find(ed[j].ss) != path[i].end()) addedge(i, j);
				if (path[j].find(ed[i].ff) != path[j].end()) addedge(i, j);
				if (path[j].find(ed[i].ss) != path[j].end()) addedge(j, i);
			}
		}
		queue<int> que;
		for (int i = 1;i <= n;i++) {
			if (deg[i] == 0) que.push(i);
		}
		int cnt = 0;
		while (que.size()) {
			int cur = que.front();que.pop();
			cnt++;
			for (int v:g[cur]) {
				if (--deg[v] == 0) que.push(v);
			}
		}
		cout << (cnt == n ? "Yes" : "No") << "\n";	
	}
}

• 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