Submission #677325

#	Time	Username	Problem	Language	Result	Execution time	Memory
677325		PositiveDelta	Jail (JOI22_jail)	C++17	26 / 100	86 ms	3900 KiB

jail

#include <bits/stdc++.h>
using namespace std;
 
const int N = 120005;

// https://codeforces.com/blog/entry/110222
template <int N, int C>
struct graph {
  int val[N + C], go[N + C];
  int ptr, sz;

  int size() {
    return sz; 
  }

  void init(int n) {
    sz = n;
    fill(val, val + n, -1);
    fill(go, go + n, -1);
    ptr = n;
  }

  void add_edge(int u, int v) {
    if (val[u] != -1) {
      val[ptr] = val[u];
      go[ptr] = go[u];
      go[u] = ptr++;
    }
    val[u] = v;
  }

  template <class UnaryFunction>  
  UnaryFunction walk(int u, UnaryFunction f) {
    int current = u;
    while (current != -1 && val[current] != -1) {
      f(val[current]);
      current = go[current];
    }
    return f;
  }
};

graph<N, N> g;

struct LCA {
  int n;
  vector<int> depth;
  vector<vector<int>> 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]];
 
    g.walk(u, [&](int v) {
      if (v != dp[0][u]) {
        dp[0][v] = u;
        dfs(v);
      }
    });
  }
 
  LCA() {
    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;
  g.init(n);
  for (int i = 0; i < n - 1; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    g.add_edge(u, v);
    g.add_edge(v, 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;
    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 {
    sort(p.begin(), p.end());
    for (int i = 0; i + 1 < m; i++)
      if (p[i + 1].second <= p[i].second) {
        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: 5 / 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