oj.uz

Submission #631511

# Submission time Handle Problem Language Result Execution time Memory
631511 2022-08-18T08:05:35 Z LittleCube Jail (JOI22_jail) C++14
0 / 100
 124 ms 216528 KB 
#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[8000005], fr[1200005], to[1200005], Hhead[1200005], Hsz[1200005], Hpos[1200005], idx, ts;
pii io[1200005];
vector<int> E[1200005], topo[8000005];

struct HLD
{
	// 0: start, 1: end
	int root[1600005][2] = {};
	int l[8000005] = {};
	int r[8000005] = {};
	
	void init()
	{
		for(int i = 1; i <= 6 * N; i++)
			l[i] = r[i] = 0;
		for(int i = 1; i <= N; i++)
			root[i][0] = root[i][1] = 0;
		for(int i = 1; i <= N; i++)
			if(Hsz[i])
			{
				root[i][0] = ++idx;
				segInit(idx, 1, Hsz[i], 0);
				root[i][1] = ++idx;
				segInit(idx, 1, Hsz[i], 1);
			}
	}

	void segInit(int i, int L, int R, int type)
	{
		if(L == R)
			return;
		int mid = (L + R) / 2;
		l[i] = ++idx;
		segInit(l[i], L, mid, type);
		r[i] = ++idx;
		segInit(r[i], mid + 1, R, type);

		if(type == 0)
		{
			topo[l[i]].emplace_back(i);
			topo[r[i]].emplace_back(i);
		}
		else
		{
			topo[i].emplace_back(l[i]);
			topo[i].emplace_back(r[i]);
		}
	}

	void segInsert(int i, int L, int R, int pos, int j, int type)
	{
		if(L == R)
		{
			if(type == 0)
				topo[j].emplace_back(i);
			else 
				topo[i].emplace_back(j);
		}
		else
		{
			int mid = (L + R) / 2;
			if(pos <= mid)
				segInsert(l[i], L, mid, pos, j, type);
			else
				segInsert(r[i], mid + 1, R, pos, j, type);
		}
	}

	void segEdge(int i, int L, int R, int j, int mL, int mR, int type)
	{
		if(mL <= L && R <= mR)
		{
			if(type == 0)
				topo[i].emplace_back(j);
			else 
				topo[j].emplace_back(i);
		}
		else if(R < mL || mR < L)
			return;
		else
		{
			int mid = (L + R) / 2;
			segEdge(l[i], L, mid, j, mL, mR, type);
			segEdge(r[i], mid + 1, R, j, mL, mR, type);
		}
	}
}hld;

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

void decompose(int u, int h)
{
	int deep = 0;
	Hhead[u] = h;
	for(int v : E[u])
		if(pre[u] != v)
		{
			if(dis[v] > dis[deep])
				deep = v;
		}
	for(int v : E[u])
		if(pre[u] != v)
		{
			Hpos[v] = (v == deep ? Hpos[u] + 1 : 1);
			decompose(v, (v == deep ? h : 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]);
}

bool isSubtree(int r, int c)
{
	return io[r].F <= io[c].F && io[c].S <= io[r].S;
}

void solve()
{
	ts = 0, idx = 0;
	cin >> N;
	for(int i = 1; i <= N; i++)
	{
		pre[i] = dis[i] = s[i] = e[i] = Hhead[i] = Hsz[i] = Hpos[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);
	}
	
	dfs(1);
	Hpos[1] = 1;
	decompose(1, 1);

	cin >> M;
	idx = M;

	for(int i = 1; i <= N; i++)
		Hsz[Hhead[i]] = max(Hsz[Hhead[i]], Hpos[i]);
	
	hld.init();

	for(int i = 1; i <= idx; i++)
	{
		deg[i] = 0;
		topo[i].clear();
	}
	
	

	for(int i = 1; i <= M; i++)
	{
		cin >> fr[i] >> to[i];
		s[fr[i]] = i;
		e[to[i]] = i;
		hld.segInsert(hld.root[Hhead[fr[i]]][0], 1, Hsz[Hhead[fr[i]]], Hpos[fr[i]], i, 0);
		hld.segInsert(hld.root[Hhead[to[i]]][1], 1, Hsz[Hhead[to[i]]], Hpos[to[i]], i, 1);
	}
	for(int i = 1; i <= M; i++)
	{
		int u = fr[i], v = to[i];
		addedge(u, i);
		addedge(v, i);

		if(pre[u] == v || pre[v] == u) continue;

		int cancelUp = 1;
		
		if(isSubtree(u, v))
			v = pre[v];
		else if(isSubtree(v, u))
			u = pre[u];
		else
			u = pre[u], v = pre[v], cancelUp = 0;

		while(Hhead[u] != Hhead[v])
		{
			if(dis[Hhead[u]] < dis[Hhead[v]])
				swap(u, v);
			hld.segEdge(hld.root[Hhead[u]][0], 1, Hsz[Hhead[u]], i, 1, Hpos[u], 0);
			hld.segEdge(hld.root[Hhead[u]][1], 1, Hsz[Hhead[u]], i, 1, Hpos[u], 1);
			u = pre[Hhead[u]];
		}
		
		if(dis[u] > dis[v]) swap(u, v);

		hld.segEdge(hld.root[Hhead[u]][0], 1, Hsz[Hhead[u]], i, Hpos[u] + cancelUp, Hpos[v], 0);
		hld.segEdge(hld.root[Hhead[u]][1], 1, Hsz[Hhead[u]], i, Hpos[u] + cancelUp, Hpos[v], 1);


	}

	for(int i = 1; i <= idx; i++)
		for(int j : topo[i])
		{	
		
			deg[j]++;
		}
	queue<int> q;
	for(int i = 1; i <= idx; i++)
		if(deg[i] == 0)
			q.emplace(i);

	for(int t = 1; t <= idx; 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.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 216396 KB Output is correct
2 Correct 98 ms 216340 KB Output is correct
3 Correct 100 ms 216420 KB Output is correct
4 Incorrect 124 ms 216440 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 216392 KB Output is correct
2 Correct 103 ms 216416 KB Output is correct
3 Incorrect 101 ms 216528 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 216392 KB Output is correct
2 Correct 103 ms 216416 KB Output is correct
3 Incorrect 101 ms 216528 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 216392 KB Output is correct
2 Correct 103 ms 216416 KB Output is correct
3 Incorrect 101 ms 216528 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 216392 KB Output is correct
2 Correct 103 ms 216416 KB Output is correct
3 Incorrect 101 ms 216528 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 216452 KB Output is correct
2 Correct 114 ms 216432 KB Output is correct
3 Correct 100 ms 216472 KB Output is correct
4 Correct 101 ms 216436 KB Output is correct
5 Incorrect 117 ms 216464 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 216396 KB Output is correct
2 Correct 98 ms 216340 KB Output is correct
3 Correct 100 ms 216420 KB Output is correct
4 Incorrect 124 ms 216440 KB Output isn't correct
5 Halted 0 ms 0 KB -