Submission #631409

#	Time	Username	Problem	Language	Result	Execution time	Memory
631409		LittleCube	Jail (JOI22_jail)	C++14	72 / 100	5087 ms	832252 KiB

jail

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;

int T, N, M, pre[1200005], dis[1200005], s[1200005], e[1200005], deg[1200005], fr[1200005], to[1200005];
vector<int> E[1200005], topo[1200005];

void dfs(int u)
{
	for(int v : E[u])
		if(pre[u] != v)
		{
			pre[v] = u;
			dis[v] = dis[u] + 1;
			dfs(v);
		}
}

void addedge(int pos, int i)
{
	if(s[pos] && s[pos] != i)
		topo[s[pos]].emplace_back(i);
	if(e[pos] && e[pos] != i)
		topo[i].emplace_back(e[pos]);
}

void solve()
{
	cin >> N;
	for(int i = 1; i <= N; i++)
	{
		pre[i] = dis[i] = s[i] = e[i] = 0;
		E[i].clear();
	}
	for(int i = 1; i < N; i++)
	{
		int u, v;
		cin >> u >> v;
		E[u].emplace_back(v);
		E[v].emplace_back(u);
	}
	cin >> M;
	for(int i = 1; i <= M; i++)
	{
		deg[i] = 0;
		topo[i].clear();
	}
	dfs(1);
	for(int i = 1; i <= M; i++)
	{
		cin >> fr[i] >> to[i];
		s[fr[i]] = i;
		e[to[i]] = i;
	}
	for(int i = 1; i <= M; i++)
	{
		addedge(fr[i], i);
		addedge(to[i], i);
		while(fr[i] != to[i])
		{
			if(dis[fr[i]] < dis[to[i]])
				swap(fr[i], to[i]);
			fr[i] = pre[fr[i]];
			addedge(fr[i], i);
		}
	}
	for(int i = 1; i <= M; i++)
		for(int j : topo[i])
			deg[j]++;
	queue<int> q;
	for(int i = 1; i <= M; i++)
		if(deg[i] == 0)
			q.emplace(i);
	for(int t = 1; t <= M; t++)
	{
		if(q.empty())
		{
			cout << "No\n";
			return;
		}
		int u = q.front();
		q.pop();
		for(int v : topo[u])
		{
			deg[v]--;
			if(deg[v] == 0)
				q.emplace(v);
		}
	}
	cout << "Yes\n";
}



signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> T;
	while(T--)
	{
		solve();
	}
}

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