oj.uz

Submission #867153

# Submission time Handle Problem Language Result Execution time Memory
867153 2023-10-27T18:58:32 Z nima_aryan Jail (JOI22_jail) C++17
0 / 100
 74 ms 1164 KB 
/**
 *    author:  NimaAryan
 *    created: 2023-10-27 20:13:43
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int Q;
  cin >> Q;
  while (Q--) {
    int N;
    cin >> N;
    vector<vector<int>> t(N);
    for (int i = 0; i < N - 1; ++i) {
      int A, B;
      cin >> A >> B;
      --A, --B;
      t[A].push_back(B);
      t[B].push_back(A);
    }
    int M;
    cin >> M;
    vector<int> S(M), T(M);
    vector<int> whoS(N, -1), whoT(N, -1);
    for (int i = 0; i < M; ++i) {
      cin >> S[i] >> T[i];
      --S[i], --T[i];
      whoS[S[i]] = i;
      whoT[T[i]] = i;
    }

    vector up(32, vector<int>(N, -1));
    vector<int> par(N), dep(N);

    /* i -> S(j), i <- T(j) */
    vector<vector<int>> d(M);
    int m = M;
    auto add_edge = [&](int a, int b) {
      if (a == m || b == m) {
        d.emplace_back();
      }
      if (a == -1 || b == -1) {
        return;
      }
      d[a].push_back(b);
    };
    vector fakeS(32, vector<int>(N, -1));
    vector fakeT(32, vector<int>(N, -1));
    auto dfs = [&](auto self, int v, int p) -> void {
      par[v] = up[0][v] = p;
      if (whoS[v] != -1) {
        fakeS[0][v] = whoS[v];
      }
      if (whoT[v] != -1) {
        fakeT[0][v] = whoT[v];
      }
      for (int k = 1; k < 32; ++k) {
        int mid = up[k - 1][v];
        if (mid == -1) {
          break;
        }
        up[k][v] = up[k - 1][mid];
        add_edge(m, fakeS[k - 1][v]);
        add_edge(m, fakeS[k - 1][mid]);
        fakeS[k][v] = m++;
        add_edge(fakeT[k - 1][v], m);
        add_edge(fakeT[k - 1][mid], m);
        fakeT[k][v] = m++;
      }
      for (int u : t[v]) {
        if (u != p) {
          dep[u] = dep[v] + 1;
          self(self, u, v);
        }
      }
    };
    dfs(dfs, 0, -1);

    auto jump = [&](int& at, int x) {
      for (int k = 0; k < 32; ++k) {
        assert(at != -1);
        if (x >> k & 1) {
          at = up[k][at];
        }
      }
    };
    auto LCA = [&](int a, int b) {
      if (dep[a] < dep[b]) {
        swap(a, b);
      }
      jump(a, dep[a] - dep[b]);
      if (a == b) {
        return a;
      }
      for (int t = 32 - 1; t >= 0; --t) {
        int na = up[t][a];
        int nb = up[t][b];
        if (na != nb) {
          a = na;
          b = nb;
        }
      }
      return par[a];
    };

    for (int i = 0; i < M; ++i) {
      int lca = LCA(S[i], T[i]);
      for (int x : {S[i], T[i]}) {
        if (x == lca) {
          continue;
        }
        x = par[x];
        for (int t = 32 - 1; t >= 0; --t) {
          int y = up[t][x];
          if (y != -1 && dep[y] > dep[lca]) {
            add_edge(i, fakeS[t][x]);
            add_edge(fakeT[t][x], i);
            x = y;
          }
        }
      }
      if (whoS[T[i]] != -1) {
        add_edge(i, whoS[T[i]]);
      }
      if (whoT[S[i]] != -1) {
        add_edge(whoT[S[i]], i);
      }
    }

    vector<int> vis(m);
    bool fail = false;
    auto check = [&](auto self, int v) -> void {
      vis[v] = 1;
      for (int u : d[v]) {
        if (!vis[u]) {
          self(self, u);
        } else if (vis[u] == 1) {
          fail = true;
        }
      }
      vis[v] = 2;
    };
    for (int i = 0; i < m; ++i) {
      if (!vis[i]) {
        check(check, i);
      }
    }
    cout << (fail ? "No" : "Yes") << "\n";
  }
  return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 360 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Incorrect 74 ms 1164 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 8 ms 1036 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 8 ms 1036 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 8 ms 1036 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 8 ms 1036 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 452 KB Output is correct
5 Incorrect 21 ms 668 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 360 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Incorrect 74 ms 1164 KB Output isn't correct
5 Halted 0 ms 0 KB -