Submission #1179272

#TimeUsernameProblemLanguageResultExecution timeMemory
1179272tch1cherinJail (JOI22_jail)C++20
0 / 100
5 ms11592 KiB
#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] = {}; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...