Submission #1309857

#TimeUsernameProblemLanguageResultExecution timeMemory
1309857thuhienneJail (JOI22_jail)C++20
Compilation error
0 ms0 KiB
#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],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];
}


vector <int> graph[maxn * 2 * (LOG + 1)];

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++) if (up[i][j]) {
			norm[i][j] = ++nodecount;
			rev[i][j] = ++nodecount;
		}
		
		if (j == 0) {
			for (int i = 1;i <= n;i++) {
				for (int x : startat[i]) {
					addedge(norm[i][j],x);
				}
				for (int x : endat[i]) {
					addedge(x,rev[i][j]);
				}
			}
		} else {
			for (int i = 1;i <= n;i++) {
				addedge(norm[i][j],norm[i][j - 1]);
				addedge(norm[i][j],norm[up[i][j - 1]][j - 1]);
				
				addedge(rev[i][j - 1],rev[i][j]);
				addedge(rev[up[i][j - 1]][j - 1],rev[i][j]);
			}
		}
		
	}
}

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

int color[maxn * 2 * (LOG + 1)];
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].push_back(i);
		endat[path[i].second].push_back(i);
	}
	
	dfs(1,-1);
	
	nodecount = m;
	createsparse();
	
	for (int i = 1;i <= m;i++) {
		int w = lca(path[i].first,path[i].second);
		
		if (dis(path[i].first,path[i].second) == 1) continue;
		
		process(path[i].first,h[path[i].first] - h[w] + 1,i);
		process(path[i].second,h[path[i].second] - h[w] + 1,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].clear();endat[i].clear();
		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 <= n * 2 * (LOG + 1);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();
	}

}

Compilation message (stderr)

jail.cpp: In function 'void solve()':
jail.cpp:124:21: error: 'dis' was not declared in this scope; did you mean 'div'?
  124 |                 if (dis(path[i].first,path[i].second) == 1) continue;
      |                     ^~~
      |                     div