Submission #546537

#	Time	Username	Problem	Language	Result	Execution time	Memory
546537		inksamurai	Jail (JOI22_jail)	C++17	100 / 100	2373 ms	457344 KiB

jail

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define rng(i,x,n) for(int i=x;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3x2WzQf ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e
 
void slv(){
	int n;
	cin>>n;
	
	vec(vi) adj(n);
	// bool pok=0;
	rep(i,n-1){
		int u,v;
		cin>>u>>v;
		u-=1,v-=1;
		// pok=pok or (u!=v-1);
		adj[u].pb(v);
		adj[v].pb(u);
	}

	// assert(pok);
	
	int m;
	cin>>m;
	vec(pii) rbts;
	rep(i,m){
		int s,t;
		cin>>s>>t;
		s-=1,t-=1;
		rbts.pb({s,t});
	}

	// fill depth
	vi parent(n,0),depth(n,0),tin(n,0),tout(n,0);
	int tmer=0;
	{
		auto dfs=[&](auto self,int v,int par)->void{
			tin[v]=tmer++;
			for(auto u:adj[v]){
				if(u==par) continue;
				parent[u]=v;
				depth[u]=depth[v]+1;
				self(self,u,v);
			}
			tout[v]=tmer++;
		};
		dfs(dfs,0,-1);
	}

	// fill sparse table
	vec(vi) spr(18,vi(n)),ids,iids;
	ids=iids=spr;
	vi d0(n),d1(n);
	{
		rep(j,18){
			rep(v,n){
				spr[j][v]=!j?parent[v]:spr[j-1][spr[j-1][v]];
			}
		}
		int num=0;
		rep(v,n){
			d0[v]=num++;
		}
		rep(v,n){
			d1[v]=num++;
		}
		rep(t,2){
			rep(j,18){
				rep(v,n){
					if(!t) ids[j][v]=num++;
					else iids[j][v]=num++;
				}
			}
		}
		// print(num);
	}

	// add corressponding edges to it's ranges
	vec(vi) gph(50*n+m);
	rep(v,n){
		int up=spr[0][v];
		gph[d0[up]].pb(ids[0][v]);
		gph[d0[v]].pb(ids[0][v]);
		gph[iids[0][v]].pb(d1[up]);
		gph[iids[0][v]].pb(d1[v]);
	}
	rep(j,17){
		rep(v,n){
			int up=ids[j+1][v]; // next level node
			gph[ids[j][v]].pb(up);
			int par=ids[j][spr[j][v]]; // vertex after jump
			gph[par].pb(up);
			// if(v==2 and j==0) print(ids[j][v],ids[j][spr[j][v]],up);

			int iup=iids[j+1][v]; // next level inversed node
			gph[iup].pb(iids[j][v]);
			par=iids[j][spr[j][v]]; // vertex after jump
			gph[iup].pb(par);
		}
	}

	// debug junk
	{
		// // 0 1 2 3 4 5 6 7 
		// // 8 9 10 11 12 13 14 15 
		// // 16 17 18 19 20 21 22 23 

		// rep(j,2){
		// 	rep(v,n){
		// 		if(j==1){
		// 			cout<<ids[j][v]<<"\n";
		// 			for(auto u:gph[ids[j][v]]){
		// 				cout<<u<<" ";
		// 			}
		// 			cout<<"\n";
		// 		}
		// 		// cout<<ids[j][v]<<" ";
		// 	}

		// 	cout<<"\n";
		// }
	}

	auto ancestor=[&](int u,int v)->bool{
		return tin[u]<=tin[v] and tout[v]<=tout[u];
	};

	auto lca=[&](int s,int t)->int{
		if(ancestor(s,t)) return s;
		if(ancestor(t,s)) return t;
		int u=t;
		per(j,17){
			if(!ancestor(spr[j][u],s)){
				u=spr[j][u];
			}
		}
		return spr[0][u];
	};

	rep(i,m){
		auto [s,t]=rbts[i];
		int now_id=50*n+i;
		gph[now_id].pb(d0[s]);
		gph[d1[t]].pb(now_id);
	}

	auto add_edge=[&](int v,int up,int id){
		gph[d0[v]].pb(id);
		gph[id].pb(d1[v]);
		per(j,17){
			int u=spr[j][v];
			if(depth[u]>=depth[up]){
				gph[ids[j][v]].pb(id);
				gph[id].pb(iids[j][v]);
				v=u;
			}
		}
	};

	// for(auto u:gph[1]){
	// 	print(u);
	// }

	vi ss(n,-1),tt(n,-1);
	rep(i,m){
		auto [s,t]=rbts[i];
		ss[s]=50*n+i;
		tt[t]=50*n+i;
	}

	rep(i,m){
		auto [s,t]=rbts[i];
		int anc=lca(s,t);
		int now_id=50*n+i;
		if(tt[s]!=-1){
			// print(tt[s]);
			gph[now_id].pb(tt[s]);
		}
		if(ss[t]!=-1){
			// print(ss[t]);
			gph[ss[t]].pb(now_id);
		}
		if(ancestor(s,t) or ancestor(t,s)){
			if(ancestor(t,s)) swap(s,t);
			// print("here");
			t=spr[0][t];
			int id=now_id,up=s;
			int v=t;
			if(s!=t){
				// print(t);
				// print(d0[t],id);
				// print(id,d1[t]);
				gph[d0[t]].pb(id);
				gph[id].pb(d1[t]);
			}
			per(j,17){
				int u=spr[j][v];
				if(depth[u]>depth[up]){
					// print(v,u,j,ids[j][v],id);
					// print(v,u,s,t,j,ids[j+1][v],id);
					gph[ids[j][v]].pb(id);
					gph[id].pb(iids[j][v]);
					v=u;
				}
			}
		}else{
			// print("here");
			if(depth[s]-depth[anc]>=1){
				s=spr[0][s];
				add_edge(s,anc,now_id);
			}
			if(depth[t]-depth[anc]>=1){
				t=spr[0][t];
				add_edge(t,anc,now_id);
			}
		}
	}

	auto has_cyc=[&]()->bool{
		vi usd(50*n+m,0),usd1(50*n+m,0);
		bool cyc=0;
		auto dfs=[&](auto self,int v)->void{
			usd[v]=1;
			usd1[v]=1;
			// print(v);
			for(auto u:gph[v]){
				if(usd1[u]){
					// print(u,v);
					cyc=1;
				}
				if(!usd[u]){
					self(self,u);
				}
			}
			usd1[v]=0;
		};
		// dfs(dfs,0);
		rep(v,50*n+m){
			if(!usd[v]){
				dfs(dfs,v);
			}
		}
		return cyc;
	};

	int res=has_cyc();
	// print(res);
	print(res?"No":"Yes");
}
 
signed main(){
_3x2WzQf;
	int t;
	cin>>t;
	rep(cs,t){
		slv();
	}
//	
	return 0;
}

• 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