Submission #1033782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033782		abczz	Jail (JOI22_jail)	C++17	100 / 100	554 ms	122136 KiB

jail

#include <iostream>
#include <vector>
#include <array>
#include <queue>
#define ll long long

using namespace std;

vector <ll> adj[120000];
vector <ll> E[480000];
vector <array<ll, 2>> paths;
ll ls[480000], rs[480000];
vector <ll> V[120000];
queue <ll> Q;
ll n, m, a, b, c, cnt, nodecnt, sz[120000], D[120000], G[120000], GID[120000], X[120000], A[120000], B[120000], in[480000], bl[120000][18];
struct ST{
  ll rt, g;
  ll build(ll id, ll l, ll r) {
    if (l == r) return A[V[g][l]];
    id = ++nodecnt;
    ll mid = (l+r)/2;
    ls[id] = build(ls[id], l, mid);
    rs[id] = build(rs[id], mid+1, r);
    if (ls[id] != -1) E[id].push_back(ls[id]);
    if (rs[id] != -1) E[id].push_back(rs[id]);
    return id;
  }
  ll rbuild(ll id, ll l, ll r) {
    if (l == r) return B[V[g][l]];
    id = ++nodecnt;
    ll mid = (l+r)/2;
    ls[id] = rbuild(ls[id], l, mid);
    rs[id] = rbuild(rs[id], mid+1, r);
    if (ls[id] != -1) E[ls[id]].push_back(id);
    if (rs[id] != -1) E[rs[id]].push_back(id);
    return id;
  }
  void link(ll id, ll l, ll r, ll ql, ll qr, ll qid) {
    if (qr < l || r < ql || id == -1) return;
    else if (ql <= l && r <= qr) {
      E[qid].push_back(id);
      return;
    }
    ll mid = (l+r)/2;
    link(ls[id], l, mid, ql, qr, qid);
    link(rs[id], mid+1, r, ql, qr, qid);
  }
  void rlink(ll id, ll l, ll r, ll ql, ll qr, ll qid) {
    if (qr < l || r < ql || id == -1) return;
    else if (ql <= l && r <= qr) {
      E[id].push_back(qid);
      return;
    }
    ll mid = (l+r)/2;
    rlink(ls[id], l, mid, ql, qr, qid);
    rlink(rs[id], mid+1, r, ql, qr, qid);
  }
}FST[120000], RST[120000];
void dfs_sz(ll u, ll p) {
  sz[u] = 1;
  for (auto v : adj[u]) {
    if (v != p) {
      D[v] = D[u] + 1;
      dfs_sz(v, u);
      sz[u] += sz[v];
      bl[v][0] = u;
    }
  }
}
void hld(ll u, ll p, ll k) {
  G[u] = k, GID[u] = V[k].size();
  V[k].push_back(u);
  ll mx = -1, id = -1;
  for (auto v : adj[u]) {
    if (v != p) {
      if (sz[v] > mx) {
        mx = sz[v], id = v;
      }
    }
  }
  if (id != -1) hld(id, u, k);
  for (auto v : adj[u]) {
    if (v != p && v != id) {
      X[cnt+1] = u;
      hld(v, u, ++cnt);
    }
  }
}
void jump(ll u, ll t, ll id) {
  //cout << u << " -> " << t << " " << id << endl;
  if (D[u] < D[t]) return;
  if (G[u] == G[t]) {
    FST[G[u]].link(FST[G[u]].rt, 0, V[G[u]].size()-1, GID[t], GID[u], id);
  }
  else {
    FST[G[u]].link(FST[G[u]].rt, 0, V[G[u]].size()-1, 0, GID[u], id);
    jump(X[G[u]], t, id);
  }
}
void rjump(ll u, ll t, ll id) {
  //cout << u << " <- " << t << " " << id << endl;
  if (D[u] < D[t]) return;
  if (G[u] == G[t]) {
    RST[G[u]].rlink(RST[G[u]].rt, 0, V[G[u]].size()-1, GID[t], GID[u], id);
  }
  else {
    RST[G[u]].rlink(RST[G[u]].rt, 0, V[G[u]].size()-1, 0, GID[u], id);
    rjump(X[G[u]], t, id);
  }
}
ll lca(ll a, ll b) {
  if (D[a] > D[b]) swap(a, b);
  ll db = D[b];
  for (int j=17; j>=0; --j) {
    if (db - (1LL<<j) >= D[a]) {
      db -= (1LL<<j);
      b = bl[b][j];
    }
  }
  for (int j=17; j>=0; --j) {
    if (bl[a][j] != bl[b][j]) {
      a = bl[a][j], b = bl[b][j];
    }
  }
  if (a != b) return bl[a][0];
  else return a;
}
ll find(ll a, ll d) {
  for (int j=17; j>=0; --j) {
    if (D[a] - (1LL<<j) >= d) {
      a = bl[a][j];
    }
  }
  return a;
}
void solve() {
  paths.clear();
  cin >> n;
  cnt = 0;
  for (int i=0; i<4*n; ++i) {
    E[i].clear();
    ls[i] = rs[i] = -1;
    in[i] = 0;
  }
  for (int i=0; i<n; ++i) {
    adj[i].clear();
    V[i].clear();
    A[i] = B[i] = -1;
    D[i] = 0;
    X[i] = G[i] = GID[i] = -1;
  }
  for (int i=0; i<n-1; ++i) {
    cin >> a >> b;
    --a, --b;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }
  cin >> m;
  nodecnt = m-1;
  for (int i=0; i<m; ++i) {
    cin >> a >> b;
    --a, --b;
    A[a] = i, B[b] = i;
    paths.push_back({a, b});
  }
  dfs_sz(0, -1);
  hld(0, -1, 0);
  for (int j=1; j<18; ++j) {
    for (int i=0; i<n; ++i) {
      bl[i][j] = bl[bl[i][j-1]][j-1];
    }
  }
  for (int i=0; i<=cnt; ++i) {
    FST[i].g = RST[i].g = i;
    FST[i].rt = FST[i].build(1, 0, V[i].size()-1);
    RST[i].rt = RST[i].rbuild(1, 0, V[i].size()-1);
  }
  int i = 0;
  for (auto [a, b] : paths) {
    c = lca(a, b);
    if (a == c) {
      jump(b, find(b, D[c]+1), i);
      rjump(bl[b][0], c, i);
    }
    else if (b == c) {
      jump(bl[a][0], c, i);
      rjump(a, find(a, D[c]+1), i);
    }
    else {
      jump(bl[a][0], c, i);
      rjump(a, c, i);
      jump(b, c, i);
      rjump(bl[b][0], c, i); 
    }
    ++i;
  }
  for (int i=0; i<=nodecnt; ++i) {
    for (auto v : E[i]) {
      //cout << i << " " << v << endl;
      ++in[v];
    }
  }
  for (int i=0; i<=nodecnt; ++i) {
    if (!in[i]) Q.push(i);
  }
  ll cur = 0;
  while (!Q.empty()) {
    auto u = Q.front();
    Q.pop();
    ++cur;
    for (auto v : E[u]) {
      --in[v];
      if (!in[v]) Q.push(v);
    }
  }
  if (cur != nodecnt+1) cout << "No\n";
  else cout << "Yes\n";
}
ll t;
int main() {
  cin >> t;
  while (t--) solve();
}

• 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