| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 890866 | 2023-12-22T04:30:23 Z | vjudge1 | Jail (JOI22_jail) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
#define ll long long
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define mpa make_pair
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define bc back()
#define ar array
#define vll vector<ll>
using namespace std;/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;*/
template <class _T>
bool chmin(_T &x, const _T &y){
if(x>y){
x=y;
return true;
}
return false;
}
template <class _T>
bool chmax(_T &x, const _T &y){
bool flag=false;
if (x<y){
x=y;flag|=true;
}
return flag;
}
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const ll inf=2e18+7;
const ll mod=1e9+7;
const ll N=2e5+7;
const ld eps=1e-9;
vector<vll> g(N);
ll d[N],p[N][20];
ll tin[N],tout[N],t;
void dfs(ll v){
tin[v]=++t;
for(ll i=1;i<19;i++) p[v][i]=p[p[v][i-1]][i-1];
for(auto i : g[v]){
if(p[v][0]==i)continue;
p[i][0]=v;
d[i]=d[v]+1;
dfs(i);
}
tout[v]=++t;
}
ll lca(ll a,ll b){
if(d[b]>d[a])swap(a,b);
ll i;
for(i=18;i>=0;i--){
if(d[a]-d[b]>=(1ll<<i) && d[p[a][i]]-d[a]==(1ll<<i)){
a=p[a][i];
}
}
if(a==b)return b;
for(i=18;i>=0;i--){
if(p[a][i]!=p[b][i] && d[p[a][i]]-d[a]==(1ll<<i)){
a=p[a][i];
b=p[b][i];
}
}
return p[a][0];
}
bool par(ll p,ll ch){
return (tin[p]<=tin[ch] && tout[ch]<=tout[p]);
}
bool between(ll a,ll x,ll y){
ll lc=lca(x,y);
if(!par(lc,a))return false;
if(par(a,x) || par(a,y))return true;
return false;
}
void solve(){
ll i,j;
ll n,m;
ll a,b;
cin>>n;
for(i=1;i<=n;i++){
g[i].clear();
for(j=0;j<20;j++)p[i][j]=0;
d[i]=tin[i]=t=tout[i]=0;
}
bool bamboo=true;
for(i=1;i<n;i++){
cin>>a>>b;
g[a].pb(b);
g[b].pb(a);
if(a+1!=b)bamboo=false;
}
if(bamboo){
cin>>m;
ll l=0;
vector<pair<ll,ll>> v;
for(i=0;i<m;i++){
cin>>a>>b;
v.pb({a,b});
}
sort(all(v));
for(i=0;i<m;i++){
a=v[i].fr,b=v[i].sc;
if(b<=l){
cout<<"No"<<endl;
return;
}
l=max(l,b);
}
cout<<"Yes"<<endl;
return;
}
dfs(1);
cin>>m;
vector<pair<ll,ll>> p(m);
for(i=0;i<m;i++) cin>>p[i].fr>>p[i].sc;
bool dp[(1ll<<(m+5))];
memset(dp,false,sizeof(dp));
dp[0]=true;
vector<vll> v(m+5);
for(ll mask=0;mask<(1ll<<m);mask++){
ll c=0;
for(i=0;i<m;i++){
if(mask&(1ll<<i))c++;
}
v[c].pb(mask);
}
for(i=1;i<=m;i++){
for(auto j : v[i]){
vector<ll> cur;
for(ll bit=0;bit<m;bit++){
if(j&(1ll<<bit)){
cur.pb(bit);
}
}
for(auto x : cur){
if(!dp[j^(1ll<<x)])continue;
vll path;
ll a=p[x].fr,b=p[x].sc;
ll lc=lca(a,b);
path.pb(lc);
while(a!=lc){
path.pb(a);
a=p[a][0];
}
while(b!=lc){
path.pb(b);
b=p[b][0];
}
for(auto a : path){
bool flag=true;
for(auto y : cur){
if(x==y)continue;
if(between(p[y].sc,p[x].fr,p[x].sc) || between(a,p[y].fr,p[y].sc)){
flag=false;
break;
}
}
if(flag){
dp[j]=true;
break;
}
}
}
}
}
if(dp[(1ll<<m)-1])cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
signed main(){
start();
ll t=1;
cin>>t;
while(t--) solve();
return 0;
}
/*
1
7
1 2
2 3
3 4
4 5
3 6
6 7
2
4 1
5 7
*/