Submission #1179272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179272		tch1cherin	Jail (JOI22_jail)	C++20	0 / 100	5 ms	11592 KiB

jail

#include <bits/stdc++.h>
using namespace std;

constexpr int MAX_N = 120000;

vector<int> graph[MAX_N];
vector<array<int, 2>> start_graph[MAX_N], end_graph[MAX_N * 2];
int color_start[MAX_N], color_end[MAX_N * 2];

int S[MAX_N], T[MAX_N];
int tin[MAX_N], tout[MAX_N], parent[MAX_N], sizes[MAX_N], head[MAX_N];
int start_path[MAX_N], end_path[MAX_N];
int N, M, tin_x = 0;

void dfs(int u, int par) {
  parent[u] = par;
  if (par != -1) {
    graph[u].erase(find(graph[u].begin(), graph[u].end(), par));
  }
  sizes[u] = 1;
  for (int v : graph[u]) {
    dfs(v, u);
    sizes[u] += sizes[v];
  }
  for (int &v : graph[u]) {
    if (sizes[v] > sizes[graph[u][0]]) {
      swap(v, graph[u][0]);
    }
  }
}

void build_hld(int u) {
  tin[u] = tin_x++;
  for (int v : graph[u]) {
    head[v] = (v == graph[u][0] ? head[u] : v);
    build_hld(v); 
  }
  tout[u] = tin_x;
}

bool is_ancestor(int u, int v) {
  return tin[u] <= tin[v] && tout[v] <= tout[u];
}

void build_graphs() {
  for (int i = N - 1; i > 0; i--) {
    for (int d = 0; d < 2; d++) {
      if (i * 2 + d < N) {
        start_graph[i * 2 + d].push_back({i, 0});  
      } else if (start_path[i * 2 + d - N] != -1) {
        start_graph[i * 2 + d].push_back({N + start_path[i * 2 + d - N], 1});
      }
      if (i * 2 + d < N) {
        end_graph[i].push_back({i * 2 + d, 0});
      } else if (end_path[i * 2 + d - N] != -1) {
        end_graph[i].push_back({N + end_path[i * 2 + d - N], 0});
      }
    }
  }
}

void add_edge_start(int u, int l, int r) {
  for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
    if (l & 1) {
      if (l < N) {
        start_graph[l].push_back({N + u, 1});
      } else if (start_path[l - N] != -1) {
        end_graph[N + start_path[l - N]].push_back({N + u, 0});
      }
      ++l;
    }
    if (r & 1) {
      --r;
      if (r < N) {
        start_graph[r].push_back({N + u, 1});
      } else if (start_path[r - N] != -1) {
        end_graph[N + start_path[r - N]].push_back({N + u, 0});
      }
    }   
  }
}

void add_edge_end(int u, int l, int r) {
  for (l += N, r += N; l < r; l >>= 1, r >>= 1) {
    if (l & 1) {
      if (l < N) {
        end_graph[N + u].push_back({l, 0});
      } else if (end_path[l - N] != -1) {
        end_graph[N + u].push_back({N + end_path[l - N], 0});
      }
      ++l;
    }
    if (r & 1) {
      --r;
      if (r < N) {
        end_graph[N + u].push_back({r, 0});
      } else if (end_path[r - N] != -1) {
        end_graph[N + u].push_back({N + end_path[r - N], 0});
      }
    }
  }
}

bool color_dfs(int u, int side) {
  if (side == 0) {
    color_start[u] = 2;
    for (auto [v, xside] : start_graph[u]) {
      int nside = side ^ xside;
      if (nside == 0) {
        if (color_start[v] == 2) {
          return true;
        }
        if (!color_start[v] && color_dfs(v, nside)) {
          return true;
        }
      } else {
        if (color_end[v] == 2) {
          return true;
        }
        if (!color_end[v] && color_dfs(v, nside)) {
          return true;
        }
      }
    }
    color_start[u] = 1;
  } else {
    color_end[u] = 2;
    for (auto [v, xside] : end_graph[u]) {
      int nside = side ^ xside;
      if (nside == 0) {
        if (color_start[v] == 2) {
          return true;
        }
        if (!color_start[v] && color_dfs(v, nside)) {
          return true;
        }
      } else {
        if (color_end[v] == 2) {
          return true;
        }
        if (!color_end[v] && color_dfs(v, nside)) {
          return true;
        }
      }
    }
    color_end[u] = 1;
  }
  return false;
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int Q;
  cin >> Q;
  while (Q--) {
    cin >> N;
    for (int i = 0; i < N - 1; i++) {
      int A, B;
      cin >> A >> B;
      --A, --B;
      graph[A].push_back(B);
      graph[B].push_back(A);
    }
    cin >> M;
    fill(start_path, start_path + N, -1);
    fill(end_path, end_path + N, -1);
    for (int i = 0; i < M; i++) {
      cin >> S[i] >> T[i];
      --S[i], --T[i];
      start_path[S[i]] = i, end_path[T[i]] = i;
    }
    tin_x = 0;
    dfs(0, -1);
    build_graphs();
    head[0] = 0;
    build_hld(0);
    for (int i = 0; i < M; i++) {
      int s = S[i], t = T[i];
      while (!is_ancestor(head[s], t)) {
        add_edge_start(i, tin[head[s]], tin[s] + 1);
        add_edge_end(i, tin[head[s]], tin[s] + 1);
        s = parent[head[s]];
      }
      while (!is_ancestor(head[t], s)) {
        add_edge_start(i, tin[head[t]], tin[t] + 1);
        add_edge_end(i, tin[head[t]], tin[t] + 1);
        t = parent[head[t]];
      }
      if (!is_ancestor(s, t)) {
        swap(s, t);
      }
      add_edge_start(i, tin[s], tin[t] + 1);
      add_edge_end(i, tin[s], tin[t] + 1);
    }
    fill(color_start, color_start + N, 0);
    fill(color_end, color_end + 2 * N, 0);
    bool good = true;
    for (int i = 0; i < N; i++) {
      if (color_start[i] == 0 && color_dfs(i, 0)) {
        good = false;
        break;
      }
    }
    for (int i = 0; i < 2 * N; i++) {
      if (color_end[i] == 0 && color_dfs(i, 1)) {
        good = false;
        break;
      }
    }
    cout << (good ? "Yes\n" : "No\n");
    for (int i = 0; i < N; i++) {
      graph[i] = {};
    }
    for (int i = 0; i < N; i++) {
      start_graph[i] = end_graph[i] = end_graph[i + N] = {};
    }
  }
}

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