Submission #660210

#	Time	Username	Problem	Language	Result	Execution time	Memory
660210		Sohsoh84	Jail (JOI22_jail)	C++17	100 / 100	2205 ms	400452 KiB

jail

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 12e4 + 10;
const ll LOG = 20;

int n, m, t, tin[MAXN], tout[MAXN], S[MAXN], T[MAXN], Par[MAXN][LOG], col[MAXN * LOG * 2],
    tn, gin[MAXN][LOG], gout[MAXN][LOG], H[MAXN], ind_S[MAXN], ind_T[MAXN];
vector<int> adj[MAXN], G[MAXN * LOG * 2];
bool flag = false;

inline void clear() {
	for (int i = 0; i < n + 5; i++) {
		tin[i] = tout[i] = S[i] = T[i] = H[i] = ind_S[i] = ind_T[i] = 0;
		memset(Par[i], 0, sizeof Par[i]);
		memset(gin[i], 0, sizeof gin[i]);
		memset(gout[i], 0, sizeof gout[i]);
		adj[i].clear();
	}
	
	for (int i = 0; i < tn + 10; i++) {
		col[i] = 0;
		G[i].clear();
	}

	n = m = t = tn = 0;
	flag = false;
}

void dfs(int v, int p) {
	H[v] = H[p] + 1;
	tin[v] = ++t;
	Par[v][0] = p;

	for (int u : adj[v])
		if (u != p)
			dfs(u, v);

	tout[v] = t;
}

inline bool par(int u, int v) {
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}

inline int LCA(int u, int v) {
	if (par(u, v)) return u;
	if (par(v, u)) return v;

	for (int i = LOG - 1; i >= 0; i--)
		if (Par[u][i] != 0 && !par(Par[u][i], v))
			u = Par[u][i];

	return Par[u][0];
}

inline int k_par(int v, int k) {
	for (int i = LOG - 1; i >= 0; i--)
		if (k & (1 << i))
			v = Par[v][i];
	return v;
}

inline vector<pll> decomp(int v, int h) {
	vector<pll> ans;
	for (int i = LOG - 1; i >= 0; i--) {
		if (h & (1 << i)) {
			ans.push_back({v, i});
			v = Par[v][i];
		}
	}

	return ans;
}

void cyc(int v) {
	col[v] = 1;
	for (int u : G[v]) {
		if (!col[u]) cyc(u);
		else if (col[u] == 1) flag = true;
	}

	col[v] = 2;
}

inline vector<pll> path_decomp(int u, int v) { // -u
	if (u == v) return {};
	if (par(u, v)) u = k_par(v, H[v] - H[u] - 1);
	else u = Par[u][0];

	int lca = LCA(u, v);
	vector<pll> ans = decomp(u, H[u] - H[lca] + 1), tans = decomp(v, H[v] - H[lca] + 1);
	for (auto e : tans) ans.push_back(e);

	return ans;
}

inline int solve() {	
	clear();

	cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	cin >> m;
	for (int i = 1; i <= m; i++) {
		cin >> S[i] >> T[i];
		ind_S[S[i]] = i;
		ind_T[T[i]] = i;
	}

	dfs(1, 0);
	for (int v = 1; v <= n; v++) {
		gin[v][0] = ind_S[v];	
		gout[v][0] = ind_T[v];	
	}

	tn = n;

	for (int i = 1; i < LOG; i++) {
		for (int v = 1; v <= n; v++) {
			int p = Par[v][i - 1];
			Par[v][i] = Par[p][i - 1];

			if (gin[v][i - 1] || gin[p][i - 1]) {
				tn++;
				if (gin[v][i - 1]) G[gin[v][i - 1]].push_back(tn);
				if (gin[p][i - 1]) G[gin[p][i - 1]].push_back(tn);

				gin[v][i] = tn;
			} 

			if (gout[v][i - 1] || gout[p][i - 1]) {
				tn++;
				if (gout[v][i - 1]) G[tn].push_back(gout[v][i - 1]);
				if (gout[p][i - 1]) G[tn].push_back(gout[p][i - 1]);
				
				gout[v][i] = tn;
			}
		}
	}

	// check 0
	for (int i = 1; i <= m; i++) {
		vector<pll> svec = path_decomp(S[i], T[i]), tvec = path_decomp(T[i], S[i]);
		for (auto [v, j] : svec) {
			if (gin[v][j]) 
				G[gin[v][j]].push_back(i);
		}

		for (auto [v, j] : tvec) {
			if (gout[v][j])
				G[i].push_back(gout[v][j]);
		}
	}

	for (int i = 1; i <= tn; i++) {
		if (!col[i])
			cyc(i);
	}

	cout << (flag ? "No" : "Yes") << endl;
	return 0;
}

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

• 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