Submission #544541

#	Time	Username	Problem	Language	Result	Execution time	Memory
544541		benson1029	Jail (JOI22_jail)	C++14	100 / 100	2342 ms	348616 KiB

jail

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

int q, n, m;
int timer = 0;
int st[120005], ed[120005];
int s[120005], t[120005];
int pst[120005], ped[120005];
vector<int> edg[120005], cyc[4200005];
int lift[120005][17];
int vis[4200005];
bool ans;

void dfs(int x, int p) {
	st[x] = ++timer;
	lift[x][0] = p;
	for(int i=1; i<=16; i++) {
		if(lift[x][i-1]==-1) lift[x][i] = -1;
		else lift[x][i] = lift[lift[x][i-1]][i-1];
	}
	for(int i:edg[x]) {
		if(i!=p) dfs(i, x);
	}
	ed[x] = ++timer;
}

bool anc(int x, int y) {
	return st[x]<=st[y] && ed[x]>=ed[y];
}

int lca(int x, int y) {
	if(anc(x, y)) return x;
	for(int i=16; i>=0; i--) {
		if(lift[x][i]==-1) continue;
		if(!anc(lift[x][i], y)) x = lift[x][i];
	}
	return lift[x][0];
}

void dfs2(int x) {
//	cout << x << " start\n";
	vis[x] = 1;
	for(int i:cyc[x]) {
		if(vis[i] == 1) {
//			cout << "gg " << i << "\n";
			ans = false;
		}
		if(!vis[i]) dfs2(i);
	}
	vis[x] = 2;
//	cout << x << " end\n"; 
}

void solve() {
	cin >> n;
	for(int i=1; i<=n; i++) edg[i].clear();
	for(int i=1; i<=35*n; i++) cyc[i].clear();
	for(int i=1; i<n; i++) {
		int u,v;
		cin >> u >> v;
		edg[u].push_back(v);
		edg[v].push_back(u);
	}
	dfs(1, -1);
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=16; j++) {
			cyc[n*(j+1) + i].push_back(n*(j-1+1) + i);
			if(lift[i][j-1] != -1)
				cyc[n*(j+1) + i].push_back(n*(j-1+1) + lift[i][j-1]); 
			
			cyc[n*(j-1+18) + i].push_back(n*(j+18) + i);
			if(lift[i][j-1] != -1)
				cyc[n*(j-1+18) + lift[i][j-1]].push_back(n*(j+18) + i); 
		}
	}
	cin >> m;
	for(int i=1; i<=m; i++) {
		cin >> s[i] >> t[i];
		pst[s[i]] = i;
		ped[t[i]] = i;
	}
	for(int i=1; i<=m; i++) {
		cyc[i].push_back(n*18 + t[i]);
		cyc[n*1 + s[i]].push_back(i);
		cyc[n*18 + s[i]].push_back(i);
		cyc[i].push_back(n*1 + t[i]);
		
		int l = lca(s[i], t[i]);
		
		int p = lift[s[i]][0];
		
		if(p!=-1) {
			if(!anc(p, l)) {
				for(int j=16; j>=0; j--) {
					if(lift[p][j]==-1) continue;
					if(!anc(lift[p][j], l)) {
						cyc[n*(18+j) + p].push_back(i);
						cyc[i].push_back(n*(1+j) + p);
						p = lift[p][j];
					}
				}
				cyc[n*18 + p].push_back(i);
				cyc[i].push_back(n*1 + p);
			}
		}
		
		p = lift[t[i]][0];
		
		if(p!=-1) {
			if(!anc(p, l)) {
				for(int j=16; j>=0; j--) {
					if(lift[p][j]==-1) continue;
					if(!anc(lift[p][j], l)) {
						cyc[n*(18+j) + p].push_back(i);
						cyc[i].push_back(n*(1+j) + p);
						p = lift[p][j];
					}
				}
				cyc[n*18 + p].push_back(i);
				cyc[i].push_back(n*1 + p);
			}
		}
		
		if(pst[l] != i) cyc[i].push_back(n*1 + l);
		if(ped[l] != i) cyc[n*18 + l].push_back(i);
	}
	for(int i=1; i<=35*n; i++) vis[i] = 0;
	ans = true;
	for(int i=1; i<=35*n; i++) {
		if(!vis[i]) dfs2(i);
	}
	cout << (ans ? "Yes\n" : "No\n");
}

int main() {
	ios::sync_with_stdio(false);
	cin >> q;
	while(q--) {
		solve();
	}
}

• 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