Submission #960853

#	Time	Username	Problem	Language	Result	Execution time	Memory
960853		Trisanu_Das	Jail (JOI22_jail)	C++17	100 / 100	1171 ms	308284 KiB

jail

#include<bits/stdc++.h>
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 < 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;
 }
}

Compilation message (stderr)

jail.cpp: In function 'int main()':
jail.cpp:103:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |   for(int u = 0; u < o.size(); u++){
      |                  ~~^~~~~~~~~~

• 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