Submission #544521

#	Time	Username	Problem	Language	Result	Execution time	Memory
544521		blue	Jail (JOI22_jail)	C++17	100 / 100	1090 ms	151576 KiB

jail

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vpii = vector<pii>;

const int lg = 17;
const int INF = 1'000'000;

int N;
int M;
vi* edge;

int ct;
vi ord;
vi ordind;

vvi anc;
vi depth;
vi subtree;

void dfs(int u)
{
	ct++;
	ord[ct] = u;
	ordind[u] = ct;

	for(int v : edge[u])
	{
		if(v == anc[u][0]) continue;

		anc[v][0] = u;
		depth[v] = 1 + depth[u];

		dfs(v);

		subtree[u] += subtree[v];
	}
}

int ancestor(int u, int k)
{
	for(int e = 0; e <= lg; e++)
		if(k & (1 << e))
			u = anc[u][e];

	return u;
}

int lca(int u, int v)
{
	if(depth[u] > depth[v]) swap(u, v);

	v = ancestor(v, depth[v] - depth[u]);

	if(u == v) return u;

	for(int e = lg; e >= 0; e--)
	{
		if(anc[u][e] == anc[v][e]) continue;
		u = anc[u][e];
		v = anc[v][e];
	}

	return anc[u][0];
}




struct segtree1
{
	vector< set<pii> > markers;
	vpii bestmark;

	segtree1()
	{
		markers = vector<set<pii>>(1+4*N);
		bestmark = vector<pii>(1+4*N, {INF, -1});
	}

	void insert(int I, pii V, int i = 1, int l = 1, int r = N)
	{
		if(I < l || r < I) return;
		else if(l == r)
		{
			markers[i].insert(V);
			bestmark[i] = min(bestmark[i], V);
		}
		else
		{
			insert(I, V, 2*i, l, (l+r)/2);
			insert(I, V, 2*i+1, (l+r)/2+1, r);
			bestmark[i] = min({bestmark[i], bestmark[2*i], bestmark[2*i+1]});
		}
	}

	void erase(int I, pii V, int i = 1, int l = 1, int r = N)
	{
		if(I < l || r < I) return;
		else if(l == r)
		{
			markers[i].erase(V);
			if(markers[i].empty()) bestmark[i] = {INF, -1};
			else bestmark[i] = *markers[i].begin();

		}
		else
		{
			erase(I, V, 2*i, l, (l+r)/2);
			erase(I, V, 2*i+1, (l+r)/2+1, r);
			bestmark[i] = min(bestmark[2*i], bestmark[2*i+1]);
		}
	}

	pii rangemin(int L, int R, int i = 1, int l = 1, int r = N)
	{
		if(R < l || r < L) return {INF, -1};
		else if(L <= l && r <= R) return bestmark[i];
		else return min(rangemin(L, R, 2*i, l, (l+r)/2), rangemin(L, R, 2*i+1, (l+r)/2+1, r));
	}
};



struct segtree2
{
	vector<set<pii>> markers;

	segtree2()
	{
		markers = vector<set<pii>>(1+4*N);
	}

	void insert(int L, int R, pii V, int i = 1, int l = 1, int r = N)
	{
		if(R < l || r < L) return;
		else if(L <= l && r <= R)
		{
			markers[i].insert(V);
		}
		else
		{
			insert(L, R, V, 2*i, l, (l+r)/2);
			insert(L, R, V, 2*i+1, (l+r)/2+1, r);
		}
	}

	void erase(int L, int R, pii V, int i = 1, int l = 1, int r = N)
	{
		if(R < l || r < L) return;
		else if(L <= l && r <= R)
		{
			markers[i].erase(V);
		}
		else
		{
			erase(L, R, V, 2*i, l, (l+r)/2);
			erase(L, R, V, 2*i+1, (l+r)/2+1, r);
		}
	}

	pii pointmax(int I, int i = 1, int l = 1, int r = N)
	{
		pii curr = markers[i].empty() ? pii{-INF, -1} : *markers[i].rbegin();
		if(l == r) return curr;
		else if(I <= (l+r)/2) return max(curr, pointmax(I, 2*i, l, (l+r)/2));
		else return max(curr, pointmax(I, 2*i+1, (l+r)/2+1, r));
	}
};








vi S, T;
vi A;





segtree1 ST1;
segtree2 ST2;




bool cyclic;


void insert_prisoner(int j)
{
	// cerr << "insert prisoner " << j << '\n';
	ST1.insert(ordind[S[j]], {depth[A[j]], j});	
	ST1.insert(ordind[T[j]], {depth[A[j]], j});

	ST2.insert(ordind[T[j]], ordind[T[j]] + subtree[T[j]] - 1, {depth[T[j]], j});
}

void erase_prisoner(int j)
{
	// cerr << "erase prisoner " << j << '\n';
	ST1.erase(ordind[S[j]], {depth[A[j]], j});	
	ST1.erase(ordind[T[j]], {depth[A[j]], j});

	ST2.erase(ordind[T[j]], ordind[T[j]] + subtree[T[j]] - 1, {depth[T[j]], j});
}

vi dfsenter;
vi dfsexit;



void prisonerdfs(int u)
{
	dfsenter[u] = 1;

	bool usedfirst = 0;
	bool usedS = 0;


	erase_prisoner(u);

	while(1)
	{
		pii vp;
		if(!usedfirst)
		{
			// cerr << "type = 1\n";
			vp = ST1.rangemin(ordind[S[u]], ordind[S[u]] + subtree[S[u]] - 1);
			if(vp.first > depth[S[u]])
			{
				usedfirst = 1;
				// cerr << "continuing\n";
				continue;
			}
		}
		else if(!usedS)
		{
			// cerr << "type = 2\n";
			vp = ST2.pointmax(ordind[S[u]]);
			if(vp.first < depth[A[u]])
			{
				usedS = 1;
				// cerr << "continuing\n";
				continue;
			} 
		}
		else
		{
			// cerr << "type = 3\n";
			vp = ST2.pointmax(ordind[T[u]]);
			if(vp.first < depth[A[u]])
			{
				// cerr << "breaking\n";
				break;
			}
		}

		int v = vp.second;

		// cerr << "edge = " << u << " -> " << v << '\n';

		if(dfsenter[v] && !dfsexit[v])
		{
			cyclic = 1;
			return;
		}
		else if(dfsenter[v] && dfsexit[v])
		{
			;
		}
		else
		{	
			insert_prisoner(u);
			prisonerdfs(v);
			erase_prisoner(u);
			if(cyclic) return;
		}
	}




	erase_prisoner(u);
	dfsexit[u] = 1;
}



void run()
{
	cin >> N;
	edge = new vi[1+N];

	for(int e = 1; e <= N-1; e++)
	{
		int a, b;
		cin >> a >> b;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}

	ct = 0;
	ord = vi(1+N, 0);
	ordind = vi(1+N, 0);

	depth = vi(1+N, 0);
	anc = vvi(1+N, vi(1+lg, 0));
	subtree = vi(1+N, 1);

	anc[1][0] = 0;
	depth[1] = 1;

	dfs(1);

	for(int e = 1; e <= lg; e++)
	{
		for(int i = 0; i <= N; i++)
		{
			anc[i][e] = anc[ anc[i][e-1] ][e-1];
		}
	}

	ST1 = segtree1();
	ST2 = segtree2();

	cyclic = 0;

	cin >> M;

	S = T = vi(1+M);
	A = vi(1+M);


	for(int j = 1; j <= M; j++)
	{
		cin >> S[j] >> T[j];

		A[j] = lca(S[j], T[j]);

		insert_prisoner(j);
	}

	dfsenter = dfsexit = vi(1+M, 0);

	for(int i = 1; i <= M; i++)
	{
		if(dfsenter[i]) continue;
		prisonerdfs(i);
		if(cyclic) break;
	}

	if(cyclic) cout << "No\n";
	else cout << "Yes\n";
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int T;
	cin >> T;

	for(int t = 1; t <= T; t++)
	{
		run();
	}
}

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