제출 #890518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
890518		amirhoseinfar1385	Jail (JOI22_jail)	C++17	61 / 100	5061 ms	28176 KiB

jail

#include<bits/stdc++.h>
using namespace std;
const int maxn=120000+10,maxl=18;
vector<int>adj[maxn];
int n,m,timea=0,alln[maxn],lca[maxl][maxn],ted[maxn],high[maxn];
pair<int,int>allq[maxn],stf[maxn];

int zird(int u,int v){
	return stf[v].first<=stf[u].first&&stf[v].second>=stf[u].second;
}

int getlca(int u,int v){
	if(zird(u,v)){
		return v;
	}
	if(zird(v,u)){
		return u;
	}
	for(int i=maxl-1;i>=0;i--){
		if(lca[i][u]!=0&&zird(v,lca[i][u])==0){
			u=lca[i][u];
		}
	}
	return lca[0][u];
}

void callca(){
	for(int i=1;i<maxl;i++){
		for(int j=1;j<=n;j++){
			lca[i][j]=lca[i-1][lca[i-1][j]];
		}
	}
}

void dfs(int u=1,int par=0){
	lca[0][u]=par;
	timea++;
	stf[u].first=timea;
	for(auto x:adj[u]){
		if(x!=par){
			high[x]=high[u]+1;
			dfs(x,u);
		}
	}
	stf[u].second=timea;
}

void vorod(){
	timea=0;
	cin>>n;
//	seg.clear();
	for(int i=1;i<=n;i++){
		adj[i].clear();
		alln[i]=-1;
	}
	for(int i=0;i<n-1;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++){
		ted[i]=0;
		cin>>allq[i].first>>allq[i].second;
		alln[allq[i].first]=i;
		alln[allq[i].second]=i;
	}	
}

int dis(int u,int v){
	int uv=getlca(u,v);
	return high[u]+high[v]-2*high[uv];
}

int din(int uv,int u,int v){
	int a=dis(u,v),b=dis(uv,u),c=dis(uv,v);
	//cout<<uv<<" "<<u<<" "<<v<<" "<<a<<" "<<b<<" "<<c<<endl;
	if(b+c==a){
		return 1;
	}
	return 0;
}


void psolve(){
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			if(i!=j){
				//cout<<i<<" "<<j<<" wtf "<<allq[i].first<<" "<<allq[i].second<<" "<<allq[j].first<<" "<<allq[j].second<<"\n";
				if(din(allq[j].first,allq[i].first,allq[i].second)){
					ted[i]++;
				}
				if(din(allq[i].second,allq[j].first,allq[j].second)){
					ted[i]++;
				}
			}
		}
	}
	set<pair<int,int>>st;
	for(int i=1;i<=m;i++){
		//cout<<"now: "<<ted[i]<<" "<<i<<"\n";
		st.insert(make_pair(ted[i],i));
	}
	while((int)st.size()>0){
		auto x=*st.begin();
		if(x.first!=0){
			//cout<<x.first<<" "<<x.second<<endl;
			cout<<"No\n";
			return ;
		}
		st.erase(x);
		int i=x.second;
		for(int j=1;j<=m;j++){
			if(i!=j){
				if(din(allq[i].first,allq[j].first,allq[j].second)){
					st.erase(make_pair(ted[j],j));
					ted[j]--;
					st.insert(make_pair(ted[j],j));
				}
				if(din(allq[j].second,allq[i].first,allq[i].second)){
					st.erase(make_pair(ted[j],j));
					ted[j]--;
					st.insert(make_pair(ted[j],j));
				}
			}
		}
	}
	cout<<"Yes\n";
	return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	for(int asd=0;asd<t;asd++){
		vorod();
		dfs();
		callca();
		psolve();
	}
}

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