Submission #1185896

#TimeUsernameProblemLanguageResultExecution timeMemory
1185896catch_me_if_you_canJail (JOI22_jail)C++20
72 / 100
1975 ms1114112 KiB
#include<bits/stdc++.h> using namespace std; #define in array<int, 2> #define pb push_back #define pob pop_back #define fast() ios_base::sync_with_stdio(false); cin.tie(NULL) struct graph { vector<vector<int>> adj; vector<int> sp; vector<vector<int>> adj_rev; int N; vector<bool> vis; vector<int> order; int SUM; void reset() { adj.clear(); adj_rev.clear(); adj.pb({}); adj_rev.pb({}); sp.assign(1, 0); vis.clear(); order.clear(); SUM = 0; N = 0; return; } int create(int k = 0) { adj.pb({}); adj_rev.pb({}); sp.pb(k); return ++N; } void add(int i, int j) { adj[i].pb(j); adj_rev[j].pb(i); return; } void dfs(int u) { //cout << "Running u = " << u << endl; if(vis[u]) return; vis[u] = 1; for(int v: adj[u]) { //cout << "Descending into v = " << v << endl; dfs(v); } order.pb(u); return; } void dfs_rev(int u) { //cout << u << endl; if(vis[u]) return; vis[u] = 1; SUM+=sp[u]; for(int v: adj_rev[u]) dfs_rev(v); return; } bool check_cycle() { //cout << "N = " << N << "\n"; vis.assign(N+1, false); for(int i = 1; i <= N; i++) { if(vis[i]) continue; dfs(i); } reverse(order.begin(), order.end()); vis.assign(N+1, false); for(int u: order) { //cout << "Curr = u = " << u << endl; if(vis[u]) continue; SUM = 0; dfs_rev(u); if(SUM >= 2) return false; } return true; } }; graph work; const int LOGM = 17; const int MX = 12e4+1; const int INF = 1e6; int pa[LOGM][MX]; int lab[2][LOGM][MX]; vector<int> adj[MX]; int tin[MX], tout[MX]; int TIMER; void dfs(int u, int p) { tin[u] = ++TIMER; pa[0][u] = p; for(int i = 1; i < LOGM; i++) pa[i][u] = pa[i-1][pa[i-1][u]]; for(int v: adj[u]) { if(v==p) continue; dfs(v, u); } tout[u] = TIMER; return; } int LCA(int u, int v) { if(tin[u] > tin[v]) swap(u, v); if(tout[u] >= tout[v]) return u; for(int i = LOGM-1; i >= 0; i--) { if(tout[pa[i][u]] < tin[v]) u = pa[i][u]; } return pa[0][u]; } int conjure(int t, int i, int u) { if(lab[t][i][u]) return lab[t][i][u]; if((lab[t][i][u] == 0) && (i == 0)) return -1; int x = conjure(t, i-1, u); int y = conjure(t, i-1, pa[i-1][u]); if((x == -1) && (y == -1)) return -1; int z = work.create(); if(x != -1) { if(t == 0) work.add(z, x); else work.add(x, z); } if(y != -1) { if(t == 0) work.add(z, y); else work.add(y, z); } return z; } void add_edge(int x, int t, int i, int u) { if(lab[t][i][u] == 0) { int s = conjure(t, i, u); if(s == -1) return; lab[t][i][u] = s; } if(t == 0) work.add(x, lab[t][i][u]); else work.add(lab[t][i][u], x); return; } void upd_edge(int x, int u, int p) { for(int i = LOGM-1; i >= 0; i--) { if(tin[pa[i][u]] > tin[p]) { add_edge(x, 0, i, u); add_edge(x, 1, i, u); u = pa[i][u]; } } add_edge(x, 0, 0, u); add_edge(x, 1, 0, u); return; } signed main() { fast(); int q; cin >> q; while(q--) { int n; cin >> n; for(int i = 1; i <= n; i++) adj[i].clear(); for(int i = 0; i < LOGM; i++) { for(int j = 0; j <= n; j++) { for(int t = 0; t < 2; t++) pa[i][j] = lab[t][i][j] = 0; } } work.reset(); int m = n-1; while(m--) { int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } vector<array<int, 3>> sp; cin >> m; while(m--) { int S, E; cin >> S >> E; int id = work.create(1); sp.pb({id, S, E}); lab[0][0][S] = id; lab[1][0][E] = id; } TIMER = 0; tin[0] = -INF; tout[0] = INF; dfs(1, 0); for(auto [id, u, v]: sp) { //cout << id << " " << u << " " << v << endl; int w = LCA(u, v); //cout << w << endl; upd_edge(id, u, w); upd_edge(id, v, w); add_edge(id, 0, 0, w); add_edge(id, 1, 0, w); } if(work.check_cycle()) cout << "Yes\n"; else cout << "No\n"; } return 0; }
#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...