Submission #1189695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189695		epicci23	Jail (JOI22_jail)	C++20	100 / 100	968 ms	163732 KiB

jail

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 1e6 + 5;

vector<int> v[N],g[N];
int n,m,depth[N],vis[N],S[N],T[N],tin[N],ti,par[N],sub[N],tail[N],p[N],inv[N],xd[N],ptr;
array<int,2> ar[N];
bool ok = 1;

inline void Add_Edge(int a,int b){
  //cout << "eklendi : " << a << ' ' << b << '\n';
  if(a != b) g[a].push_back(b);
}

void dfs(int c,int p){
  par[c] = p;
  for(int x : v[c]){
    if(x == p) continue;
    depth[x] = depth[c] + 1;
    dfs(x, c);
  }
}

void Prep(int c,int p){
  sub[c] = 1;
  for(int x : v[c]){
    if(x == p) continue;
    Prep(x, c);
    sub[c] += sub[x];
  }
}

void HLD(int c,int p,int h){
  tail[c] = h, xd[c] = ti;
  tin[ti++] = c;
  int ne = -1;

  //cout << "suan : " << c << " tim : " << xd[c] << " tail : " << tail[c] << '\n';

  for(int u : v[c]){
    if(u == p) continue;
    if(ne == -1 || sub[u] > sub[ne]) ne = u;
  }

  if(ne != -1) HLD(ne, c, h);

  for(int u : v[c]){
    if(u == p || u == ne) continue;
    //cout << "lmao\n";
    HLD(u, c, u);
  }
}

void Create(int rt,int l,int r){
  p[rt] = ++ptr;
  //cout << "tree1 : " << l << ' ' <<  r << ' ' << p[rt] << '\n';
  if(l == r){
    if(S[tin[l]] != -1){
     Add_Edge(p[rt], S[tin[l]]);
     //cout << "ilginc : " << l << ' ' << S[tin[l]] << '\n';
    }
    return;
  }

  int mid = (l + r) / 2;
  Create(rt * 2, l, mid), Create(rt * 2 + 1, mid + 1, r);

  Add_Edge(p[rt], p[rt * 2]);
  Add_Edge(p[rt], p[rt * 2 + 1]);
}

void Create2(int rt,int l,int r){
  inv[rt] = ++ptr;
  //cout << "tree2 : " << l << ' ' <<  r << ' ' << inv[rt] << '\n';
  if(l == r){
    if(T[tin[l]] != -1){
      Add_Edge(T[tin[l]], inv[rt]);
     // cout << "ilginc2 : " << l << ' ' << T[tin[l]] << '\n';
    }
    return;
  }

  int mid = (l + r) / 2;
  Create2(rt * 2, l, mid), Create2(rt * 2 + 1, mid + 1, r);

  Add_Edge(inv[rt * 2], inv[rt]);
  Add_Edge(inv[rt * 2 + 1], inv[rt]);
}

void Add(int rt,int l,int r,int gl,int gr,int nd,bool gg){
  if(r < gl || l > gr) return;
  if(l >= gl && r <= gr){
    if(gg){
      Add_Edge(nd, p[rt]);
      //cout << "eklendi : " << "!" << nd << ' ' << l << ' ' << r  << '\n';
    }
    else{
      Add_Edge(inv[rt], nd);
      //cout << "eklendi : " << l << ' ' <<  r << ' ' << "!" << nd << '\n';
    }
    return;
  }
  int mid = (l + r) / 2;
  Add(rt * 2, l, mid, gl, gr, nd, gg), Add(rt * 2 + 1, mid + 1, r, gl, gr, nd, gg);
}

void Find(int c){
  if(vis[c] == 2 || !ok) return;
  if(vis[c] == 1){
    ok = 0;
    return;
  }
  vis[c] = 1;
  for(int u : g[c]) Find(u); 
  vis[c] = 2;
}

inline void Hm(int l,int r,int nd){
  int ln = xd[ar[nd][0]];
  if(ln >= l && ln <= r){
    if(l < ln) Add(1,1,n,l,ln-1,nd,1);
    if(ln < r) Add(1,1,n,ln+1,r,nd,1);
  }
  else Add(1,1,n,l,r,nd,1);
 
  ln = xd[ar[nd][1]];
  if(ln >= l && ln <= r){
    if(l < ln) Add(1,1,n,l,ln-1,nd,0);
    if(ln < r) Add(1,1,n,ln+1,r,nd,0);
  }
  else Add(1,1,n,l,r,nd,0);
}

void _(){
  cin >> n;
  ok = ti = 1;
  
  for(int i=0;i<=min(N-1,8*n);i++){
  	vis[i] = sub[i] = 0;
  	v[i].clear(),g[i].clear();
  	S[i] = T[i] = -1;
  }

  for(int i=1;i<n;i++){
  	int a,b;
  	cin >> a >> b;
  	v[a].push_back(b);
  	v[b].push_back(a);
  }

  dfs(1, 1);
  Prep(1, 1);
  HLD(1, 1, 1);
  
  cin >> m;
  ptr = m;

  for(int i=1;i<=m;i++){
  	cin >> ar[i][0] >> ar[i][1];
  	S[ar[i][0]] = i;
  	T[ar[i][1]] = i;
  }

  Create(1, 1, n);
  Create2(1, 1, n);

  for(int i=1;i<=m;i++){
    int a = ar[i][0], b = ar[i][1];
    for(;tail[a]!=tail[b]; b = par[tail[b]]){
      if(depth[tail[a]] > depth[tail[b]]) swap(a, b);
      Hm(xd[tail[b]], xd[b], i);
    }
    if(depth[a] > depth[b]) swap(a, b);
    Hm(xd[a], xd[b], i);
  }

  /*for(int i=1;i<=m;i++){
    int a = ar[i][0], b = ar[i][1];

    while(a != b){
      if(depth[a] < depth[b]) swap(a, b);
      if(T[a] != -1) g[T[a]].push_back(i);
      if(S[a] != -1) g[i].push_back(S[a]);     
      a = par[a];
    }

    if(T[a] != -1) g[T[a]].push_back(i);
    if(S[a] != -1) g[i].push_back(S[a]);
  }*/
  
  for(int i=1;i<=ptr;i++){
    sort(all(g[i]));
    g[i].erase(unique(all(g[i])),g[i].end());
  }

  for(int i=1;i<=ptr;i++) Find(i);
  
  
  if(ok) cout << "Yes\n";
  else cout << "No\n";
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;cin >> tc;
  while(tc--) _();
  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