Submission #1018118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018118		Unforgettablepl	Jail (JOI22_jail)	C++17	100 / 100	2385 ms	449840 KiB

jail

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

#define int long long


void solve(){
	int n;
	cin >> n;
	vector<vector<int>> adj(n+1);
	for(int i=1;i<n;i++){
		int a,b;cin>>a>>b;
		adj[a].emplace_back(b);
		adj[b].emplace_back(a);
	}
	vector<int> depth(n+1);
	vector<vector<int>> p(n+1,vector<int>(17));
	vector<vector<int>> exitnode(n+1,vector<int>(17));
	vector<vector<int>> entrynode(n+1,vector<int>(17));
	function<void(int,int,int)> dfs = [&](int x,int par,int dep){
		depth[x]=dep;
		p[x][0]=par;
		for(int&i:adj[x])if(i!=par)dfs(i,x,dep+1);
	};
	vector<vector<int>> secadj;
	int nodes = 0;
	auto allot = [&](){
		secadj.emplace_back();
		return nodes++;
	};
	for(int i=1;i<=n;i++){
		entrynode[i][0] = allot();
		exitnode[i][0] = allot();
	}
	dfs(1,0,1);
	for(int bit=1;bit<17;bit++){
		for(int i=1;i<=n;i++){
			p[i][bit] = p[p[i][bit-1]][bit-1];
			entrynode[i][bit] = allot();
			secadj[entrynode[i][bit]].emplace_back(entrynode[i][bit-1]);
			secadj[entrynode[i][bit]].emplace_back(entrynode[p[i][bit-1]][bit-1]);
			exitnode[i][bit] = allot();
			secadj[exitnode[i][bit-1]].emplace_back(exitnode[i][bit]);
			secadj[exitnode[p[i][bit-1]][bit-1]].emplace_back(exitnode[i][bit]);
		}
	}
	auto lca = [&](int a,int b){
		if(depth[a]<depth[b])swap(a,b);
		int tar = depth[a]-depth[b];
		for(int bit=0;bit<17;bit++)if(tar&(1<<bit))a=p[a][bit];
		for(int bit=16;bit>=0;bit--)if(p[a][bit]!=p[b][bit]){
			a = p[a][bit];
			b = p[b][bit];
		}
		if(a==b)return a;
		return p[a][0];
	};
	auto liftentry = [&](int x,int tar,int node){
		for(int bit=0;bit<17;bit++)if(tar&(1<<bit)){
			secadj[node].emplace_back(entrynode[x][bit]);
			x=p[x][bit];
		}
	};
	auto liftexit = [&](int x,int tar,int node){
		for(int bit=0;bit<17;bit++)if(tar&(1<<bit)){
			secadj[exitnode[x][bit]].emplace_back(node);
			x=p[x][bit];
		}
	};
	int m;
	cin >> m;
	vector<int> s(m+1);
	vector<int> t(m+1);
	for(int i=1;i<=m;i++)cin>>s[i]>>t[i];
	for(int i=1;i<=m;i++){
		int currnode = allot();
		int currlca = lca(s[i],t[i]);
		int deplca = depth[currlca];
		liftexit(p[t[i]][0],depth[t[i]]-deplca,currnode);
		if(t[i]!=currlca)liftexit(s[i],depth[s[i]]-deplca+1,currnode);
		else liftexit(s[i],depth[s[i]]-deplca,currnode);
		liftentry(p[s[i]][0],depth[s[i]]-deplca,currnode);
		if(s[i]!=currlca)liftentry(t[i],depth[t[i]]-deplca+1,currnode);
		else liftentry(t[i],depth[t[i]]-deplca,currnode);
		secadj[entrynode[s[i]][0]].emplace_back(currnode);
		secadj[currnode].emplace_back(exitnode[t[i]][0]);
	}
	vector<int> visited(nodes);
	bool works = true;
	function<void(int)> secdfs = [&](int x){
		if(visited[x]==2)return;
		if(visited[x]==1){
			works = false;
			return;
		}
		visited[x]=1;
		for(int&i:secadj[x])secdfs(i);
		visited[x]=2;
	};
	for(int i=0;i<nodes;i++)secdfs(i);
	if(works){
		cout << "Yes\n";
	} else cout << "No\n";
}
 
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	cin >> t;
	while(t--)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