Submission #765157

#	Time	Username	Problem	Language	Result	Execution time	Memory
765157		ymm	Jail (JOI22_jail)	C++17	21 / 100	90 ms	10068 KiB

jail

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100'010;
vector<int> A[N];
vector<int> A0[N];
int st[N], ft[N];
int par[N];
int n, m;

void dfs(int v, int p, int &t)
{
	st[v] = t++;
	par[v] = p;
	for (int u : A0[v])
		if (u != p)
			dfs(u, v, t);
	ft[v] = t;
}

void add_edge(int i, int j)
{
	if (i == j)
		return;
	A[i].push_back(j);
}

vector<int> path(int i, int j)
{
	vector<int> ans;
	while (!(st[i] <= st[j] && st[j] < ft[i])) {
		ans.push_back(i);
		i = par[i];
	}
	ans.push_back(i);
	while (j != i) {
		ans.push_back(j);
		j = par[j];
	}
	return ans;
}

bool vis[N], anc[N];
bool dfs_cycle(int v)
{
	anc[v] = vis[v] = 1;
	for (int u : A[v]) {
		if (anc[u])
			return 1;
		if (vis[u])
			continue;
		if (dfs_cycle(u))
			return 1;
	}
	anc[v] = 0;
	return 0;
}

bool has_cycle()
{
	Loop (i,0,n)
		if (!vis[i] && dfs_cycle(i))
			return 1;
	return 0;
}

int s[N], t[N];
int sp[N], tp[N];

void traverse(int i)
{
	for (int u : path(s[i], t[i])) {
		if (sp[u] != -1)
			add_edge(sp[u], i);
		if (tp[u] != -1)
			add_edge(i, tp[u]);
	}
}

void init()
{
	cin >> n;
	memset(sp, -1, n*sizeof(*sp));
	memset(tp, -1, n*sizeof(*tp));
	memset(vis, 0, n*sizeof(*vis));
	memset(anc, 0, n*sizeof(*anc));
	Loop (i,0,n)
		A0[i].clear();
	Loop (i,1,n) {
		int v, u;
		cin >> v >> u;
		--v; --u;
		A0[v].push_back(u);
		A0[u].push_back(v);
	}
	cin >> m;
	Loop (i,0,m)
		A[i].clear();
	Loop (i,0,m) {
		cin >> s[i] >> t[i];
		--s[i]; --t[i];
		sp[s[i]] = i;
		tp[t[i]] = i;
	}
}

void solve()
{
	init();
	int dard = 0;
	dfs(0, -1, dard);
	Loop (i,0,m)
		traverse(i);
	cout << (has_cycle()? "No": "Yes") << '\n';
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int q;
	cin >> q;
	while (q--)
		solve();
}

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