oj.uz

Submission #1039063

# Submission time Handle Problem Language Result Execution time Memory
1039063 2024-07-30T12:01:00 Z juicy Jail (JOI22_jail) C++17
0 / 100
 54 ms 99628 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 12e4 + 5, LG = 17, MAX = 4080005;

int n, m, q, tot;
int dep[N], pr[LG][N], S[LG][N], T[LG][N], vis[MAX];
vector<int> g[N], gph[MAX];

void add(int u, int v) {
  gph[u].push_back(v);
}

void create(int j, int v) {
  S[j][v] = ++tot;
  T[j][v] = ++tot;
  if (j > 0) {
    add(S[j - 1][v], S[j][v]);
    add(S[j - 1][pr[j - 1][v]], S[j][v]);
    add(T[j][v], T[j - 1][v]);
    add(T[j][v], T[j - 1][pr[j - 1][v]]);
  }
} 

void dfs(int u) {
  for (int v : g[u]) {
    if (v != pr[0][u]) {
      dep[v] = dep[u] + 1;
      pr[0][v] = u;
      create(0, v);
      for (int j = 1; j < LG; ++j) {
        pr[j][v] = pr[j - 1][pr[j - 1][v]];
        if (dep[v] >= (1 << j)) {
          create(j, v);
        }
      }
      dfs(v);
    }
  }
}

void adds(int u, int p, int s) {
  for (int j = LG - 1; ~j; --j) {
    if (dep[u] - (1 << j) >= dep[p]) {
      add(S[j][u], S[0][s]);
      u = pr[j][u];
    }
  } 
}

void addt(int u, int p, int t) {
  for (int j = LG - 1; ~j; --j) {
    if (dep[u] - (1 << j) >= dep[p]) {
      add(T[0][t], T[j][u]);
      u = pr[j][u];
    }
  }
}

int lca(int u, int v) {
  if (dep[u] < dep[v]) {
    swap(u, v);
  }
  for (int j = LG - 1; ~j; --j) {
    if (dep[u] - (1 << j) >= dep[v]) {
      u = pr[j][u];
    }
  }
  if (u == v) {
    return u;
  }
  for (int j = LG - 1; ~j; --j) {
    if (pr[j][u] != pr[j][v]) {
      u = pr[j][u], v = pr[j][v];
    }
  }
  return pr[0][u];
}

bool cyc;

void DFS(int u) {
  vis[u] = 1;
  for (int v : gph[u]) {
    if (!vis[v]) {
      DFS(v);
      if (cyc) {
        return;
      }
    } else if (vis[v] == 1) {
      cyc = 1;
      return;
    }
  }
  vis[u] = 2;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> q;
  while (q--) {
    cin >> n;
    for (int i = 1; i < n; ++i) {
      int u, v; cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
    }
    create(0, 1);
    dep[1] = 1;
    dfs(1);
    cin >> m;
    for (int i = 1; i <= m; ++i) {
      int s, t; cin >> s >> t;
      int p = lca(s, t);
      adds(pr[0][s], p, s);
      adds(t, p == s ? s : pr[0][p], s);
      addt(pr[0][t], p, t);
      addt(s, p == t ? t : pr[0][p], t);
    }
    for (int i = 1; i <= tot && !cyc; ++i) {
      if (!vis[i]) {
        DFS(i);
      }
    }
    cout << (cyc ? "No" : "Yes") << "\n";
    cyc = 0;
    for (int i = 1; i <= n; ++i) {
      g[i].clear();
    }
    while (tot > 0) {
      gph[tot].clear();
      vis[tot] = 0;
      --tot;
    }
  }
  return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 99176 KB Output is correct
2 Correct 44 ms 99164 KB Output is correct
3 Correct 42 ms 99156 KB Output is correct
4 Incorrect 54 ms 99628 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 99156 KB Output is correct
2 Correct 42 ms 99156 KB Output is correct
3 Incorrect 47 ms 99288 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 99156 KB Output is correct
2 Correct 42 ms 99156 KB Output is correct
3 Incorrect 47 ms 99288 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 99156 KB Output is correct
2 Correct 42 ms 99156 KB Output is correct
3 Incorrect 47 ms 99288 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 99156 KB Output is correct
2 Correct 42 ms 99156 KB Output is correct
3 Incorrect 47 ms 99288 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 98996 KB Output is correct
2 Correct 43 ms 99160 KB Output is correct
3 Correct 46 ms 99156 KB Output is correct
4 Correct 43 ms 99156 KB Output is correct
5 Incorrect 49 ms 99152 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 99176 KB Output is correct
2 Correct 44 ms 99164 KB Output is correct
3 Correct 42 ms 99156 KB Output is correct
4 Incorrect 54 ms 99628 KB Output isn't correct
5 Halted 0 ms 0 KB -