Submission #677285

#	Time	Username	Problem	Language	Result	Execution time	Memory
677285		PositiveDelta	Jail (JOI22_jail)	C++17	21 / 100	79 ms	1080 KiB

jail

#include <bits/stdc++.h>
using namespace std;

struct LCA {
  int n;
  vector<int> depth;
  vector<vector<int>> g, dp;

  void dfs(int u) {
    depth[u] = (u == 0 ? 0 : depth[dp[0][u]] + 1);
    for (int i = 0; i + 1 < 20; i++)
      dp[i + 1][u] = dp[i][dp[i][u]];

    for (int v : g[u])
      if (v != dp[0][u]) {
        dp[0][v] = u;
        dfs(v);
      }
  }

  LCA(vector<vector<int>> g) : g(g) {
    n = g.size();
    depth.resize(n);
    dp.assign(20, vector<int>(n, 0));
    dfs(0);
  }

  int lca(int u, int v) {
    if (depth[u] < depth[v])
      swap(u, v);

    for (int i = 20 - 1; i >= 0; i--)
      if (depth[u] - (1 << i) >= depth[v])
        u = dp[i][u];

    if (u == v)
      return u;

    for (int i = 20 - 1; i >= 0; i--)
      if (dp[i][u] != dp[i][v]) {
        u = dp[i][u];
        v = dp[i][v];
      }

    return dp[0][u];
  }

  int dist(int u, int v) {
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
  }
};

void solve() {
  int n;
  cin >> n;
  vector<vector<int>> g(n);
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }

  int m;
  cin >> m;
  vector<pair<int, int>> p(m);
  for (auto &[a, b] : p) {
    cin >> a >> b;
    a--, b--;
  }

  if (n <= 250 && m <= 6) {
    vector<int> order(m);
    iota(order.begin(), order.end(), 0);
    LCA l(g);
    do {
      vector<bool> occupied(n, false);
      for (auto [a, b] : p)
        occupied[a] = true;

      bool bad = false;
      for (int i : order) {
        auto [a, b] = p[i];
        int lca = l.lca(a, b);
        vector<int> p1, p2;
        while (a != lca) {
          p1.push_back(a);
          a = l.dp[0][a];
        }

        while (b != lca) {
          p2.push_back(b);
          b = l.dp[0][b];
        }

        p2.push_back(lca);
        reverse(p2.begin(), p2.end());
        vector<int> path;
        for (int v : p1)
          path.push_back(v);

        for (int v : p2)
          path.push_back(v);

        int k = path.size();
        for (int j = 0; j + 1 < k; j++)
          if (occupied[path[j + 1]])
            bad = true;

        occupied[path[0]] = false;
        occupied[path.back()] = true;
      }

      if (!bad) {
        cout << "Yes\n";
        return;
      }
    } while (next_permutation(order.begin(), order.end()));
    cout << "No\n";
  } else {
    set<int> sa_inc, sb_inc, sa_dec, sb_dec;
    for (auto [a, b] : p) {
      if (a < b) {
        sa_inc.insert(a);
        sb_inc.insert(b);
      } else {
        sa_dec.insert(a);
        sb_dec.insert(b);
      }
    }

    sort(p.begin(), p.end(), [](pair<int, int> a, pair<int, int> b) {
      return a.second > b.second;
    });

    for (auto [a, b] : p) {
      if (a < b) {
        sa_inc.erase(a);
        sb_inc.erase(b);
        if (sa_dec.lower_bound(a) != sa_dec.end() || sa_inc.lower_bound(a) != sa_inc.end()) {
          cout << "No\n";
          return;
        }
      }
    }
    
    sort(p.begin(), p.end(), [](pair<int, int> a, pair<int, int> b) {
      return a.second < b.second;
    });

    for (auto [a, b] : p) {
      if (a > b) {
        sa_dec.erase(a);
        sb_dec.erase(b);
        if (sa_dec.lower_bound(b) != sa_dec.end() && *sa_dec.lower_bound(b) <= a) {
          cout << "No\n";
          return;
        }
      }
    }
    cout << "Yes\n";
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int q;
  cin >> q;
  while (q--)
    solve();
}

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23