Submission #1309999

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309999		thuhienne	Jail (JOI22_jail)	C++20	100 / 100	1831 ms	375704 KiB

jail

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

using ll = long long;

#define re exit(0);
#define norm __norm__

const int maxn = 120009;
const int LOG = 17;

int n;
vector <int> adj[maxn];
int startat[maxn],endat[maxn];
int m;
pair <int,int> path[maxn];

int h[maxn],up[maxn][LOG + 1];

int nodecount;
int norm[maxn][LOG + 1],rev[maxn][LOG + 1];

void dfs(int node,int par) {
	for (int x : adj[node]) if (x != par) {
		h[x] = h[node] + 1;
		up[x][0] = node;
		for (int i = 1;i <= LOG;i++) up[x][i] = up[up[x][i - 1]][i - 1];
		dfs(x,node);
	}
}

int lca(int u,int v) {
	if (h[u] < h[v]) swap(u,v);
	int diff = h[u] - h[v];
	for (int i = LOG;i >= 0;i--) if (diff >> i & 1) u = up[u][i];
	if (u == v) return u;
	for (int i = LOG;i >= 0;i--) if (up[u][i] != up[v][i]) {
		u = up[u][i];
		v = up[v][i];
	}
	return up[u][0];
}

int dis(int u,int v) {
	return h[u] + h[v] - 2 * h[lca(u,v)];
}

vector <int> graph[maxn * 45];

void addedge(int u,int v) {
	if (u == 0 || v == 0 || u == v) return;
	graph[u].push_back(v);
}

void createsparse() {
	
	for (int j = 0;j <= LOG;j++) {
		
		for (int i = 1;i <= n;i++) {
			norm[i][j] = ++nodecount;
			rev[i][j] = ++nodecount;
		}
		
		if (j == 0) {
			for (int i = 1;i <= n;i++) {
				addedge(norm[i][j],startat[i]);
				addedge(endat[i],rev[i][j]);
			}
		} else {
			for (int i = 1;i <= n;i++) {
				addedge(norm[i][j],norm[i][j - 1]);
				if (up[i][j - 1]) addedge(norm[i][j],norm[up[i][j - 1]][j - 1]);
				
				addedge(rev[i][j - 1],rev[i][j]);
				if (up[i][j - 1]) addedge(rev[up[i][j - 1]][j - 1],rev[i][j]);
			}
		}
		
	}
}

void addnorm(int u,int h,int index) {
	for (int i = 0;i <= LOG;i++) if (h >> i & 1) {
		addedge(index,norm[u][i]);
		u = up[u][i];
	}
}
void addrev(int u,int h,int index) {
	for (int i = 0;i <= LOG;i++) if (h >> i & 1) {
		addedge(rev[u][i],index);
		u = up[u][i];
	}
}

int color[maxn * 45];
bool circuit;

void dfs(int node) {
	color[node] = 1;
	for (int x : graph[node]) if (color[x] != 2) {
		if (color[x] == 1) {
			circuit = 1;
		} else dfs(x);
	}
	color[node] = 2;
}

void solve() {
	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 >> path[i].first >> path[i].second;
		startat[path[i].first] = i;
		endat[path[i].second] = i;
	}
	
	dfs(1,-1);
	
	nodecount = m;
	createsparse();
	
	for (int i = 1;i <= m;i++) {
		int u = path[i].first,v = path[i].second;
		int w = lca(u,v);
		
		if (v != w) {
			addrev(u,h[u] - h[w] + 1,i);
			addrev(up[v][0],h[v] - h[w],i);
		}
		else addrev(u,h[u] - h[w],i);
		
		if (u != w) {
			addnorm(v,h[v] - h[w] + 1,i);
			addnorm(up[u][0],h[u] - h[w],i);
		}
		else addnorm(v,h[v] - h[w],i);
		
	}
	
	for (int i = 1;i <= nodecount;i++) if (!color[i]) dfs(i);
	
	cout << (circuit ? "No" : "Yes") << '\n';
}

void reset() {
	for (int i = 1;i <= n;i++) {
		adj[i].clear();startat[i] = endat[i] = 0;
		h[i] = 0;
		for (int j = 0;j <= LOG;j++) up[i][j] = norm[i][j] = rev[i][j] = 0;
	}
	for (int i = 1;i <= nodecount;i++) {
		graph[i].clear();
		color[i] = 0;
	}
	circuit = 0;
}

int main() {
  ios_base::sync_with_stdio(0);cin.tie(nullptr);

	int test;cin >> test;while (test--) {
		solve();
		reset();
	}

}

• 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