Submission #544592

#	Time	Username	Problem	Language	Result	Execution time	Memory
544592		sidon	Jail (JOI22_jail)	C++17	100 / 100	3028 ms	429608 KiB

jail

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

const int Z = 1.2e5, B = 17;

int N, M;
vector<array<int, 3>> g[Z][B+1][2];
int p[Z][B], d[Z];

void dfs(int u) {
	for(const auto &[v, j, k] : g[u][B][0]) if(v != p[u][0])
		p[v][0] = u, d[v] = d[u] + 1, dfs(v);
}

int lca(int u, int v) {
	if(d[u] < d[v]) swap(u, v);
	for(int i = B; i--; )
		if((d[u] - d[v]) & (1<<i)) u = p[u][i];
	if(u == v) return u;

	for(int i = B; i--; )
		if(p[u][i] != p[v][i]) u = p[u][i], v = p[v][i];
	return p[u][0];
}

int getWithout(int u, int v) {
	if(d[u] < d[v] && lca(u, v) == u) {
		for(int i = B; i--; ) if((d[v] - d[u] - 1) & (1<<i)) v = p[v][i];
		return v;
	}
	return p[u][0];
}

int cur, ord[Z][B+1][2];
bool vis[Z][B+1][2];

void tarjan(int i, int j, int k) {
	vis[i][j][k] = 1;
	for(const auto &[x, y, z] : g[i][j][k])
		if(!vis[x][y][z]) tarjan(x, y, z);
	ord[i][j][k] = --cur;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int T; cin >> T;
	while(T--) {
		cin >> N;
		for(int i = 0; i < N; ++i)
			for(int j = 0; j <= B; ++j)
				for(int k = 0; k < 2; ++k)
					g[i][j][k].clear();
		for(int i = 1; i < N; ++i) {
			int u, v; cin >> u >> v;
			--u, --v;
			g[u][B][0].push_back({v, B, 0});
			g[v][B][0].push_back({u, B, 0});
		}

		dfs(0);
		for(int i = 1; i < B; ++i) {
			for(int u = 0; u < N; ++u) {
				p[u][i] = p[p[u][i-1]][i-1];
				for(int w : {u, p[u][i-1]}) {
					g[u][i][0].push_back({w, i-1, 0});
					g[w][i-1][1].push_back({u, i, 1});
				}
			}
		}
		for(int i = 0; i < N; ++i) g[i][B][0].clear();

		cin >> M;
		for(int i = 0; i < M; ++i) {
			int s, t; cin >> s >> t;
			--s, --t;

			g[i][B][0].push_back({s, 0, 1});
			g[t][0][0].push_back({i, B, 0});

			auto jump = [&](int &w, int j, int k) {
				if(!k) g[w][j][1].push_back({i, B, 0});
				if(k)  g[i][B][0].push_back({w, j, 0});
				w = p[w][j];
			};

			for(int k : {0, 1}) {
				int u = s, v = t;
				if(k) v = getWithout(v, u);
				else  u = getWithout(u, v);
				if(d[u] < d[v]) swap(u, v);

				for(int j = B; j--; ) if((d[u] - d[v]) & (1<<j)) {
					jump(u, j, k);
				}
				if(u != v) {
					for(int j = B; j--; ) if(p[u][j] != p[v][j]) {
						jump(u, j, k);
						jump(v, j, k);
					}
					jump(u, 0, k);
					jump(v, 0, k);
				}
				jump(u, 0, k);
			}
		}

		for(int i = 0; i < N; ++i)
			for(int j = 0; j <= B; ++j)
				vis[i][j][0] = vis[i][j][1] = 0;

		cur = 1<<30;
		for(int i = 0; i < N; ++i)
			for(int j = 0; j <= B; ++j)
				for(int k = 0; k < 2; ++k)
					if(!vis[i][j][k]) tarjan(i, j, k);

		bool ans = 1;

		for(int i = 0; i < N; ++i)
			for(int j = 0; j <= B; ++j)
				for(int k = 0; k < 2; ++k)
					for(const auto &[x, y, z] : g[i][j][k])
						if(ord[x][y][z] < ord[i][j][k]) ans = 0;

		cout << (ans ? "Yes" : "No") << '\n';
	}
}

• 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