Submission #692331

#	Time	Username	Problem	Language	Result	Execution time	Memory
692331		flappybird	Jail (JOI22_jail)	C++17	49 / 100	541 ms	481172 KiB

jail

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 2501010
#define MAXS 18
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
int N, M, K;
int sp[MAX][MAXS];
int getind(int x, int t, int istd) {
	return x * MAXS * 2 + t * 2 + istd;
}
vector<int> tree[MAX], adj[MAX];
int dep[MAX];
int S[MAX];
int T[MAX];
int deg[MAX];
int vis[MAX];
void dfs(int x) {
	int i;
	for (i = 1; i < MAXS; i++) if (~sp[x][i - 1]) sp[x][i] = sp[sp[x][i - 1]][i - 1];
	for (auto v : tree[x]) if (v != sp[x][0]) {
		sp[v][0] = x;
		dep[v] = dep[x] + 1;
		dfs(v);
	}
}
int lca(int u, int v) {
	int i;
	if (dep[u] != dep[v]) {
		if (dep[u] > dep[v]) swap(u, v);
		int d = dep[v] - dep[u];
		for (i = 0; i < MAXS; i++) if (d >> i & 1) v = sp[v][i];
	}
	if (u == v) return u;
	for (i = MAXS - 1; i >= 0; i--) if (sp[u][i] != sp[v][i]) u = sp[u][i], v = sp[v][i];
	return sp[u][0];
}
void solve() {
	cin >> N;
	int i, j;
	for (i = 0; i < N; i++) for (j = 0; j < MAXS; j++) sp[i][j] = -1;
	for (i = 0; i < N; i++) tree[i].clear();
	int a, b;
	for (i = 0; i < N - 1; i++) {
		cin >> a >> b; a--; b--;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	cin >> M;
	for (i = 0; i < M; i++) cin >> S[i] >> T[i], S[i]--, T[i]--;
	dep[0] = 1;
	dfs(0);
	int sind = getind(N - 1, MAXS - 1, 1) + 1;
	int K = sind + M;
	for (i = 0; i < K; i++) adj[i].clear(), vis[i] = 0, deg[i] = 0;
	for (j = 1; j < MAXS; j++) {
		for (i = 0; i < N; i++) {
			adj[getind(i, j - 1, 0)].push_back(getind(i, j, 0));
			adj[getind(i, j, 1)].push_back(getind(i, j - 1, 1));
			if (~sp[i][j - 1]) adj[getind(sp[i][j - 1], j - 1, 0)].push_back(getind(i, j, 0));
			if (~sp[i][j - 1]) adj[getind(i, j, 1)].push_back(getind(sp[i][j - 1], j - 1, 1));
		}
	}
	for (i = 0; i < M; i++) {
		adj[getind(T[i], 0, 1)].push_back(i + sind);
		adj[i + sind].push_back(getind(S[i], 0, 0));
		int l = lca(S[i], T[i]);
		if (l == S[i] || l == T[i]) {
			int v = S[i] + T[i] - l;
			v = sp[v][0];
			int d = dep[v];
			if (~l) d -= dep[l];
			for (j = MAXS - 1; j >= 0; j--) if (d >> j & 1) {
				adj[getind(v, j, 0)].push_back(i + sind);
				adj[i + sind].push_back(getind(v, j, 1));
				v = sp[v][j];
			}
		}
		else {
			l = sp[l][0];
			for (auto v : { sp[S[i]][0], sp[T[i]][0] }) {
				int d = dep[v];
				if (~l) d -= dep[l];
				for (j = MAXS - 1; j >= 0; j--) if (d >> j & 1) {
					adj[getind(v, j, 0)].push_back(i + sind);
					adj[i + sind].push_back(getind(v, j, 1));
					v = sp[v][j];
				}
			}
		}
		adj[i + sind].push_back(getind(S[i], 0, 1));
		adj[getind(T[i], 0, 0)].push_back(i + sind);
	}
	queue<int> q;
	for (i = 0; i < K; i++) for (auto v : adj[i]) deg[v]++;
	for (i = 0; i < K; i++) if (!deg[i]) q.push(i);
	while (q.size()) {
		int t = q.front();
		q.pop();
		if (vis[t]) continue;
		vis[t] = 1;
		for (auto v : adj[t]) {
			if (!vis[v]) {
				deg[v]--;
				if (!deg[v]) q.push(v);
			}
		}
	}
	for (i = sind; i < sind + M; i++) if (!vis[i]) {
		cout << "No" << ln;
		return;
	}
	cout << "Yes" << ln;
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int Q;
	cin >> Q;
	while (Q--) solve();
}

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