Submission #718815

#	Time	Username	Problem	Language	Result	Execution time	Memory
718815		Abrar_Al_Samit	Jail (JOI22_jail)	C++17	72 / 100	5047 ms	157912 KiB

jail

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

const int nax = 120001;
const int lg = 17;

vector<int>g[nax], t[nax];
int n, m;

int bed[nax], work[nax];
int sp[nax][lg];
int tt = 0, st[nax], en[nax];
int vis[nax], dep[nax];
vector<int>wh[nax];

void dfs(int v, int p = 1, int d = 0) {
	dep[v] = d;
	sp[v][0] = p;
	st[v] = tt++;
	for(int j=1; j<lg; ++j) {
		sp[v][j] = sp[sp[v][j-1]][j-1];
	}
	for(int u : g[v]) if(u!=p) {
		dfs(u, v, d+1);
	}
	en[v] = tt-1;
}
bool anc(int u, int v) {
	return st[u] <= st[v] && en[u] >= en[v];
}
int LIFT(int u, int v) {
	for(int j=lg-1; j>=0; --j) if(!anc(sp[u][j], v)) {
		u = sp[u][j];
	}
	if(!anc(u, v)) u = sp[u][0];
	return u;
}
bool lies(int u, int v, int lca, int x) {
	if(anc(lca, x)) {
		return anc(x, u) || anc(x, v);
	}
	return false;
}
int bond(int i, int j) {
	int lca1 = LIFT(bed[i], work[i]);
	int lca2 = LIFT(bed[j], work[j]);
	int len1 = dep[bed[i]] + dep[work[i]] - 2 * dep[lca1];
	int len2 = dep[bed[j]] + dep[work[j]] - 2 * dep[lca2];

	bool spd = false;
	if(len1 < len2) {
		spd = true;
		swap(i, j);
		swap(len1, len2);
		swap(lca1, lca2);
	}


	bool f = lies(bed[i], work[i], lca1, bed[j]);
	bool ff = lies(bed[i], work[i], lca1, work[j]);

	if(f && ff) return 1;

	if(spd) {
		swap(i, j);
		swap(len1, len2);
		swap(lca1, lca2);

		f = lies(bed[i], work[i], lca1, bed[j]);
		ff = lies(bed[i], work[i], lca1, work[j]);
	}
	if(f) {
		t[j].push_back(i);
	}
	if(ff) {
		t[i].push_back(j);
	}
	return 0;
}

int go(int v) {
	vis[v] = 1;
	for(int u : t[v]) {
		if(!vis[u]) {
			if(go(u)) return 1;
		} else {
			if(vis[u]==1) return 1;
		}
	}
	vis[v] = 2;
	return 0;
}
void PlayGround() {
	cin>>n;
	for(int i=1; i<=n; ++i) {
		g[i].clear(), t[i].clear(), tt = vis[i] = 0;
		wh[i].clear();
	}
	for(int i=0; i<n-1; ++i) {
		int u, v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1);

	cin>>m;
	for(int i=1; i<=m; ++i) {
		cin>>bed[i]>>work[i];
		wh[bed[i]].push_back(i);
		wh[work[i]].push_back(i);
	}



	for(int i=1; i<=m; ++i) {
		int lca = LIFT(bed[i], work[i]);
		int x = bed[i], y = work[i];
		while(1) {
			for(int z : wh[x]) if(z!=i) {
				if(bond(i, z)) {
					cout<<"No\n";
					return;
				}
			}
			if(x==lca) break;
			x = sp[x][0];
		}
		while(1) {
			for(int z : wh[y]) if(z!=i) {
				if(bond(i, z)) {
					cout<<"No\n";
					return;
				}
			}
			if(y==lca) break;
			y = sp[y][0];
		}
	}

	for(int i=1; i<=m; ++i) if(!vis[i]) {
		if(go(i)) {
			cout<<"No\n";
			return;
		}
	}
	cout<<"Yes\n";

	// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tc;
	cin>>tc;
	while(tc--) {
		PlayGround();
	}
	return 0;
}

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