Submission #1181000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181000		LCJLY	Jail (JOI22_jail)	C++20	72 / 100	2312 ms	1114112 KiB

jail

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

#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

vector<int>adj[120005];

int two[22][120005];
int d[120005];

void dfs(int index, int par){
	for(int x=0;x<20;x++){
		two[x+1][index]=two[x][two[x][index]];
	}
	for(auto it:adj[index]){
		if(it==par) continue;
		d[it]=d[index]+1;
		two[0][it]=index;
		dfs(it,index);
	}
}

int lca(int a, int b){
	if(d[a]>d[b]) swap(a,b);
	int diff=d[b]-d[a];
	for(int x=0;x<20;x++){
		if(diff&(1<<x)){
			b=two[x][b];
		}
	}
	if(a==b) return a;
	for(int x=19;x>=0;x--){
		if(two[x][a]!=two[x][b]){
			a=two[x][a];
			b=two[x][b];
		}
	}
	return two[0][a];
}

vector<int>st[120005];
vector<int>ed[120005];

vector<int>adj2[120005];

bool visited[120005];
bool visited2[120005];
bool cycle=false;

void dfs2(int index, int par){
	visited[index]=true;
	visited2[index]=true;
	for(auto it:adj2[index]){	
		//if(it==par) continue;
		if(visited2[it]) cycle=true;
		else if(!visited[it]){
			dfs2(it,index);
		}
	}
	visited2[index]=false;
}

void solve(){
	int n;
	cin >> n;
	
	//reset
	for(int x=0;x<=n;x++){
		adj[x].clear();
		st[x].clear();
		ed[x].clear();
		for(int y=0;y<20;y++){
			two[y][x]=0;
		}
	}
	int temp,temp2;
	for(int x=0;x<n-1;x++){
		cin >> temp >> temp2;
		adj[temp].push_back(temp2);
		adj[temp2].push_back(temp);
	}
	
	dfs(1,-1);
	
	int m;
	cin >> m;
	
	//reset
	for(int x=0;x<=m;x++){
		adj2[x].clear();
		visited[x]=0;
		visited2[x]=0;
	}
	
	pii arr[m];
	for(int x=0;x<m;x++){
		cin >> arr[x].first >> arr[x].second;
		st[arr[x].first].push_back(x);
		ed[arr[x].second].push_back(x);
	}
	
	for(int x=0;x<m;x++){
		int hold=lca(arr[x].first,arr[x].second);
		int cur=arr[x].first;
		//show(hold,hold);
		while(1){
			for(auto it:st[cur]){
				if(it==x) continue;
				adj2[it].push_back(x);
				//show2(it,it,x,x);
			}
			for(auto it:ed[cur]){
				if(it==x) continue;
				adj2[x].push_back(it);
				//show2(x,x,it,it);
			}
			if(cur==hold) break;
			cur=two[0][cur];
		}
		cur=arr[x].second;
		while(1){
			//cur=two[0][cur];
			for(auto it:st[cur]){
				if(it==x) continue;
				adj2[it].push_back(x);
				//show2(it,it,x,x);
			}
			for(auto it:ed[cur]){
				if(it==x) continue;
				adj2[x].push_back(it);
				//show2(x,x,it,it);
			}
			if(cur==hold) break;
			cur=two[0][cur];
		}
	}
	
	cycle=false;
	//cycle checking
	for(int x=0;x<m;x++){
		if(visited[x]) continue;
		dfs2(x,-1);
	}
	
	
	if(cycle) cout << "No\n";
	else cout << "Yes\n";
	
}
																   
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	cin >> t;
	while(t--){
		solve();
	}
}

• 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