Submission #701005

#	Time	Username	Problem	Language	Result	Execution time	Memory
701005		dongliu0426	Jail (JOI22_jail)	C++17	100 / 100	1750 ms	307536 KiB

jail

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

const int N=1.2e5,H=17,N_=N+2*N*H;

vector<int>g[N],q[N_];
int p[H][N],d[N],w[N_];

inline int z(int i,int h,int t){
 return (i*H+h)*2+t;
}

void dfs(int i){
 for(int h=0;h<H-1;h++){
  p[h+1][i]=p[h][p[h][i]];
  q[z(i,h,0)].push_back(z(i,h+1,0));
  q[z(p[h][i],h,0)].push_back(z(i,h+1,0));
  q[z(i,h+1,1)].push_back(z(i,h,1));
  q[z(i,h+1,1)].push_back(z(p[h][i],h,1));
 }
 for(int j:g[i])
  if(p[0][i]!=j){
   p[0][j]=i;
   d[j]=d[i]+1;
   dfs(j);
  }
}

int lca(int i,int j){
 if(d[i]<d[j])
  swap(i,j);
 int k=d[i]-d[j];
 for(int h=0;h<H;h++)
  if(k>>h&1)
   i=p[h][i];
 if(i==j)
  return i;
 for(int h=H-1;h>=0;h--)
  if(p[h][i]!=p[h][j])
   i=p[h][i],j=p[h][j];
 return p[0][i];
}


template<class F>
void up(int i,int k,const F&f) {
 if(k<0)
  return;
 for(int h=0;h<H;h++)
  if(k>>h&1)
   f(i,h),i=p[h][i];
 f(i,0);
}

int main() {
 ios::sync_with_stdio(0),cin.tie(0);
 int t;
 cin>>t;
 while(t--){
  int n;
  cin>>n;
  for(int h=0;h<n-1;h++){
   int i,j;
   cin>>i>>j,i--,j--;
   g[i].push_back(j),g[j].push_back(i);
  }
  dfs(0);
  int m;
  cin>>m;
  for(int h=0;h<m;h++){
   int i,j;
   cin>>i>>j,i--,j--;
   q[n*H*2+h].push_back(z(i,0,0));
   q[z(j,0,1)].push_back(n*H*2+h);
   int f=lca(i,j);
   if(i!=f){
    up(p[0][i],d[i]-d[f]-1,[&](int u,int v){
     q[z(u,v,0)].push_back(n*H*2+h);
    });
    up(j,d[j]-d[f]-1,[&](int u,int v){
     q[z(u,v,0)].push_back(n*H*2+h);
    });
   }else
    up(j,d[j]-d[f]-1,[&](int u,int v){
     q[z(u,v,0)].push_back(n*H*2+h);
    });
   if(j!=f){
    up(p[0][j],d[j]-d[f]-1,[&](int u,int v){
     q[n*H*2+h].push_back(z(u,v,1));
    });
    up(i,d[i]-d[f]-1,[&](int u,int v){
     q[n*H*2+h].push_back(z(u,v,1));
    });
   }else
    up(i,d[i]-d[f]-1,[&](int u,int v){
     q[n*H*2+h].push_back(z(u,v,1));
    });
  }
  for(int i=0;i<n*H*2+m;i++)
   for(int j:q[i])
    w[j]++;
  vector<int>o;
  for(int i=0;i<n*H*2+m;i++)
   if(!w[i])
    o.push_back(i);
  for(int u=0;u<(int)o.size();u++){
   int i=o[u];
   for(int j:q[i])
    if(--w[j]==0)
     o.push_back(j);
  }
  cout<<((int)o.size()==n*H*2+m?"Yes\n":"No\n");
  for(int i=0;i<n;i++)
   g[i].clear();
  for(int i=0;i<n*H*2+m;i++)
   q[i].clear(),w[i]=0;
 }
 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