제출 #1309838

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1309838		thuhienne	Jail (JOI22_jail)	C++20	61 / 100	5093 ms	25256 KiB

jail

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define re exit(0);

const int maxn = 120009;
const int LOG = 17;

int n;
vector <int> adj[maxn];
int m;
pair <int,int> path[maxn];

int h[maxn],up[maxn][LOG + 1];

void dfs(int node,int par) {
	for (int x : adj[node]) if (x != par) {
		h[x] = h[node] + 1;
		up[x][0] = node;
		for (int i = 1;i <= LOG;i++) up[x][i] = up[up[x][i - 1]][i - 1];
		dfs(x,node);
	}
}

int lca(int u,int v) {
	if (h[u] < h[v]) swap(u,v);
	int diff = h[u] - h[v];
	for (int i = LOG;i >= 0;i--) if (diff >> i & 1) u = up[u][i];
	if (u == v) return u;
	for (int i = LOG;i >= 0;i--) if (up[u][i] != up[v][i]) {
		u = up[u][i];
		v = up[v][i];
	}
	return up[u][0];
}

int dis(int u,int v) {
	return h[u] + h[v] - 2 * h[lca(u,v)];
}

bool inpath(int x,int u,int v) {
	return dis(u,x) + dis(x,v) == dis(u,v);
}

vector <int> graph[maxn];

void addedge(int u,int v) {
	graph[u].push_back(v);
}

int color[maxn];
bool circuit;

void dfs(int node) {
	color[node] = 1;
	for (int x : graph[node]) if (color[x] != 2) {
		if (color[x] == 1) {
			circuit = 1;
		} else dfs(x);
	}
	color[node] = 2;
}

void solve() {
	cin >> n;
	for (int i = 1;i < n;i++) {
		int u,v;cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	cin >> m;
	for (int i = 1;i <= m;i++) {
		cin >> path[i].first >> path[i].second;
	}
	
	dfs(1,-1);
	
	for (int i = 1;i <= m;i++) for (int j = 1;j <= m;j++) if (i != j) {
		if (inpath(path[j].first,path[i].first,path[i].second)) addedge(i,j);
		if (inpath(path[j].second,path[i].first,path[i].second)) addedge(j,i); 
	}
	
	for (int i = 1;i <= m;i++) if (!color[i]) {
		dfs(i);
	}
	cout << (circuit ? "No" : "Yes") << '\n';
}

void reset() {
	for (int i = 1;i <= n;i++) {
		adj[i].clear();
		h[i] = 0;
		for (int j = 0;j <= LOG;j++) up[i][j] = 0;
		graph[i].clear();
		color[i] = 0;
	}
	circuit = 0;
}

int main() {
  ios_base::sync_with_stdio(0);cin.tie(nullptr);

	int test;cin >> test;while (test--) {
		solve();
		reset();
	}

}

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23