oj.uz

Submission #677270

# Submission time Handle Problem Language Result Execution time Memory
677270 2023-01-02T17:26:46 Z PositiveDelta Jail (JOI22_jail) C++17
0 / 100
 29 ms 588 KB 
#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--;
  }

  vector<int> order(n);
  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";
}

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 316 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 324 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 588 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 324 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 588 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 324 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 588 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 324 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 588 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 320 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Runtime error 1 ms 452 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 316 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -