Submission #592632

#	Time	Username	Problem	Language	Result	Execution time	Memory
592632		MilosMilutinovic	Jail (JOI22_jail)	C++14	5 / 100	5042 ms	3352 KiB

jail

/**
 *    author:  wxhtzdy
 *    created: 08.07.2022 12:20:42
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int tt;
  cin >> tt;
  while (tt--) {
    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<int> s(m), t(m);
    for (int i = 0; i < m; i++) {
      cin >> s[i] >> t[i];
      --s[i]; --t[i];
    }
    const int L = 20;
    vector<vector<int>> jump(n, vector<int>(L));
    vector<int> dep(n);
    vector<int> tin(n);
    vector<int> tout(n);
    int T = 0;
    function<void(int, int)> Dfs = [&](int v, int pr) {
      dep[v] = dep[pr] + 1;
      tin[v] = ++T;
      jump[v][0] = pr;
      for (int u : g[v]) {
        if (u != pr) {
          Dfs(u, v);
        }
      }
      tout[v] = T;      
    };
    Dfs(0, 0);
    for (int j = 1; j < L; j++) {
      for (int i = 0; i < n; i++) {
        jump[i][j] = jump[jump[i][j - 1]][j - 1];
      }
    }
    auto LCA = [&](int u, int v) {
      if (dep[u] < dep[v]) {
        swap(u, v);
      }                    
      for (int i = L - 1; i >= 0; i--) {
        if (dep[jump[u][i]] >= dep[v]) {
          u = jump[u][i];
        }
      }
      for (int i = L - 1; i >= 0; i--) {
        if (jump[u][i] != jump[v][i]) {
          u = jump[u][i];
          v = jump[v][i];
        }
      }
      return u == v ? u : jump[u][0];
    };
    auto isPar = [&](int a, int b) {
      return tin[a] <= tin[b] && tout[b] <= tout[a];
    };
    auto onPath = [&](int a, int b, int c) {
      int L = LCA(b, c);
      return isPar(L, a) && (isPar(a, b) || isPar(a, c));
    };
    vector<vector<bool>> f(m, vector<bool>(m));
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < m; j++) {
        if (i == j) {
          continue;
        }
        if (onPath(s[j], s[i], t[i])) {
          f[i][j] = true;
        }
        if (onPath(t[j], s[i], t[i])) {
          f[j][i] = true;
        }
      }
    }        
    bool ok = true;
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < m; j++) {
        if (i == j) {
          continue;
        }
        if (f[i][j] && f[j][i]) {
          ok = false;
        }
      }   
    }
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < m; j++) {
        for (int k = 0; k < m; k++) {
          if (i == j || i == k || j == k) {
            continue;
          }
          if (f[i][j] && f[j][k] && f[k][i]) {
            ok = false;
          }
        }
      }
    }
    cout << (ok ? "Yes" : "No") << '\n';
  }                                                                    
  return 0;
}

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