Submission #995119

#TimeUsernameProblemLanguageResultExecution timeMemory
995119SzilJail (JOI22_jail)C++17
5 / 100
405 ms175696 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int MAXN = 200'100; vector<int> g[MAXN], g2[MAXN*21]; int pos[MAXN], tin[MAXN], tout[MAXN], head[MAXN], heavy[MAXN], sz[MAXN], par[MAXN], s[MAXN], e[MAXN], depth[MAXN], col[MAXN*21], timer, pos_timer, n, m; bool ok; void init() { for (int i = 1; i <= n; i++) { g[i].clear(); } for (int i = 1; i <= 20*n; i++) { g2[i].clear(); } fill(heavy, heavy+n+1, 0); fill(s, s+n+1, 0); fill(e, e+n+1, 0); fill(col, col+20*n+1, 0); timer = pos_timer = 1; ok = true; } int get_segtree1_index(int u) { return 10*n + u; } int get_segtree2_index(int u) { return n + u; } int get_path_index(int u) { return u; } void dfs(int u, int p = -1, int d = 0) { tin[u] = timer++; sz[u] = 1; depth[u] = d; for (int v : g[u]) { if (v == p) continue; par[v] = u; dfs(v, u, d+1); sz[u] += sz[v]; if (sz[heavy[u]] < sz[v]) { heavy[u] = v; } } tout[u] = timer++; } bool is_ancestor(int u, int v) { return tin[u] <= tin[v] && tout[v] <= tout[u]; } int nxt(int u, int v) { if (is_ancestor(u, v)) { for (int x : g[u]) { if (x != par[u] && is_ancestor(x, v)) return x; } } else { return par[u]; } } void dfs2(int u, int h, int p) { head[u] = h; pos[u] = pos_timer++; if (heavy[u]) { dfs2(heavy[u], h, u); } for (int v : g[u]) { if (v == p || v == heavy[u]) continue; dfs2(v, v, u); } } void dfs3(int u) { col[u] = 1; for (int v : g2[u]) { if (col[v] == 0) dfs3(v); else if (col[v] == 1) ok = false; } col[u] = 2; } void build_segtree1(int v, int tl, int tr) { if (tl == tr) { if (s[tl]) { g2[get_segtree1_index(v)].emplace_back(get_path_index(s[tl])); } } else { int tm = (tl + tr) / 2; build_segtree1(2*v, tl, tm); build_segtree1(2*v+1, tm+1, tr); g2[get_segtree1_index(v)].emplace_back(get_segtree1_index(2*v)); g2[get_segtree1_index(v)].emplace_back(get_segtree1_index(2*v+1)); } } void build_segtree2(int v, int tl, int tr) { if (tl == tr) { if (e[tl]) { g2[get_path_index(e[tl])].emplace_back(get_segtree2_index(v)); } } else { int tm = (tl + tr) / 2; build_segtree2(2*v, tl, tm); build_segtree2(2*v+1, tm+1, tr); g2[get_segtree2_index(2*v)].emplace_back(get_segtree2_index(v)); g2[get_segtree2_index(2*v+1)].emplace_back(get_segtree2_index(v)); } } void add_segtree1_edge(int v, int tl, int tr, int l, int r, int node) { if (l > r) return; if (l == tl && r == tr) { g2[node].emplace_back(get_segtree1_index(v)); } else { int tm = (tl + tr) / 2; add_segtree1_edge(2*v, tl, tm, l, min(tm, r), node); add_segtree1_edge(2*v+1, tm+1, tr, max(tm+1, l), r, node); } } void add_segtree2_edge(int v, int tl, int tr, int l, int r, int node) { if (l > r) return; if (l == tl && r == tr) { g2[get_segtree2_index(v)].emplace_back(node); } else { int tm = (tl + tr) / 2; add_segtree2_edge(2*v, tl, tm, l, min(tm, r), node); add_segtree2_edge(2*v+1, tm+1, tr, max(tm+1, l), r, node); } } void qry1(int u, int v, int node) { while (head[u] != head[v]) { if (depth[head[u]] < depth[head[v]]) swap(u, v); add_segtree1_edge(1, 1, n, pos[head[u]], pos[u], node); u = par[head[u]]; } if (depth[u] > depth[v]) swap(u, v); add_segtree1_edge(1, 1, n, pos[u], pos[v], node); } void qry2(int u, int v, int node) { while (head[u] != head[v]) { if (depth[head[u]] < depth[head[v]]) swap(u, v); add_segtree2_edge(1, 1, n, pos[head[u]], pos[v], node); u = par[head[u]]; } if (depth[u] > depth[v]) swap(u, v); add_segtree2_edge(1, 1, n, pos[u], pos[v], node); } void solve() { init(); cin >> n; for (int i = 0; i < n-1; i++) { int u, v; cin >> u >> v; g[u].emplace_back(v); g[v].emplace_back(u); } cin >> m; vector<pair<int, int>> edges(m+1); for (int i = 1; i <= m; i++) { cin >> edges[i].first >> edges[i].second; auto [u, v] = edges[i]; s[u] = i; e[v] = i; } build_segtree1(1, 1, n); build_segtree2(1, 1, n); dfs(1); dfs2(1, 1, -1); for (int i = 1; i <= m; i++) { auto [u, v] = edges[i]; qry1(nxt(u, v), v, get_path_index(i)); qry2(u, nxt(v, u), get_path_index(i)); } for (int i = 1; i <= m; i++) { int u = get_path_index(i); if (col[u] == 0) dfs3(u); } cout << (ok?"Yes\n":"No\n"); } int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while (t--) { solve(); } }

Compilation message (stderr)

jail.cpp: In function 'int nxt(int, int)':
jail.cpp:68:1: warning: control reaches end of non-void function [-Wreturn-type]
   68 | }
      | ^
#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...