제출 #567742

#제출 시각아이디문제언어결과실행 시간메모리
567742joshjmsJail (JOI22_jail)C++14
5 / 100
2228 ms439412 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast") #define int long long #define ld long double #define pb push_back #define fi first #define se second #define debug(x) cout << #x << " => " << x << "\n"; const long long mod = 1e9 + 7; int n, a[120005], b[120005], m, s[120005], t[120005]; vector <int> g[120005]; int par[120005][20], in[120005], out[120005], tmr; int node[120005][20][2], nodes; vector <int> dirGraph[4800005]; int vis[4800005], flag; void init() { cin >> n; for(int i = 1; i < n; i++) cin >> a[i] >> b[i]; cin >> m; for(int i = 1; i <= m; i++) cin >> s[i] >> t[i]; for(int i = 1; i <= n; i++) { g[i].clear(); in[i] = out[i] = 0; for(int j = 0; j < 20; j++) par[i][j] = 0; } for(int i = 1; i < n; i++) { g[a[i]].pb(b[i]); g[b[i]].pb(a[i]); } in[0] = -1; out[0] = 1e18; tmr = 0; for(int i = 1; i <= 40 * n; i++) { dirGraph[i].clear(); vis[i] = 0; } for(int i = 1; i <= n; i++) { for(int j = 0; j < 20; j++) { node[i][j][0] = node[i][j][1] = 0; } } nodes = 0; } void dfs(int v, int p) { par[v][0] = v; par[v][1] = p; for(int i = 2; i < 18; i++) par[v][i] = par[par[par[v][i - 1]][1]][i - 1]; in[v] = ++tmr; for(auto c : g[v]) if(c != p) dfs(c, v); out[v] = ++tmr; } void findCycle(int v) { vis[v] = 1; for(auto c : dirGraph[v]) { if(vis[c] == 1) {flag = 1; return;} if(vis[c] == 0) findCycle(c); } vis[v] = 2; } void solve () { dfs(1, 0); // for(int i = 1; i <= n; i++) { // for(int j = 0; j < 18; j++) { // cout << par[i][j] << " "; // } // cout << "\n"; // } nodes = 0; for(int i = 1; i <= n; i++) { node[i][0][0] = ++nodes; node[i][0][1] = ++nodes; } for(int i = 1; i <= m; i++) { dirGraph[node[s[i]][0][0]].pb(node[t[i]][0][1]); } for(int i = 1; i <= n; i++) { for(int j = 1; j < 18; j++) { node[i][j][0] = ++nodes; node[i][j][1] = ++nodes; // cout << "[" << i << " " << j << "] => " << node[i][j][0] << ", " << node[i][j][1] << "\n"; dirGraph[node[i][j][0]].pb(node[i][j - 1][0]); if(dirGraph[node[i][j][0]].back() == 0) dirGraph[node[i][j][0]].pop_back(); dirGraph[node[i][j][0]].pb(node[par[par[i][j - 1]][1]][j - 1][0]); if(dirGraph[node[i][j][0]].back() == 0) dirGraph[node[i][j][0]].pop_back(); dirGraph[node[i][j - 1][1]].pb(node[i][j][1]); if(dirGraph[node[i][j - 1][1]].back() == 0) dirGraph[node[i][j - 1][1]].pop_back(); dirGraph[node[par[par[i][j - 1]][1]][j - 1][1]].pb(node[i][j][1]); if(dirGraph[node[i][j - 1][1]].back() == 0) dirGraph[node[i][j - 1][1]].pop_back(); } } auto lca = [&](int u, int v) { if(in[u] <= in[v] && out[u] >= out[v]) return u; if(in[v] <= in[u] && out[v] >= out[u]) return v; for(int i = 17; i >= 0; i--) { if(in[par[u][i]] <= in[v] && out[par[u][i]] >= out[v]) continue; u = par[u][i]; } return par[u][1]; }; for(int i = 1; i <= m; i++) { int LCA = lca(s[i], t[i]); // debug(s[i]); // debug(t[i]); // debug(LCA); if(LCA == s[i]) { int u, v; u = t[i], v = s[i]; for(int j = 17; j >= 0; j--) { if(in[par[u][j]] <= in[v] && out[par[u][j]] >= out[v]) continue; dirGraph[node[s[i]][0][0]].pb(node[u][j][0]); // cout << "connect [" << u << " " << i << "]\n"; // debug(s[i]); // debug(node[s[i]][0][0]); // debug(node[u][i][0]); u = par[par[u][j]][1]; } u = par[t[i]][1], v = par[s[i]][1]; for(int j = 17; j >= 0; j--) { if(in[par[u][j]] <= in[v] && out[par[u][j]] >= out[v]) continue; dirGraph[node[u][j][1]].pb(node[s[i]][0][0]); // cout << "connect [" << u << " " << i << "]\n"; u = par[par[u][j]][1]; } } else if(LCA == t[i]) { int u, v; u = par[s[i]][1], v = par[t[i]][1]; for(int j = 17; j >= 0; j--) { if(in[par[u][j]] <= in[v] && out[par[u][j]] >= out[v]) continue; dirGraph[node[s[i]][0][0]].pb(node[u][j][0]); u = par[par[u][j]][1]; } u = s[i], v = t[i]; for(int j = 17; j >= 0; j--) { if(in[par[u][j]] <= in[v] && out[par[u][j]] >= out[v]) continue; dirGraph[node[u][j][1]].pb(node[s[i]][0][0]); u = par[par[u][j]][1]; } } else { int u, v; u = par[s[i]][1], v = par[LCA][1]; for(int j = 17; j >= 0; j--) { if(in[par[u][j]] <= in[v] && out[par[u][j]] >= out[v]) continue; dirGraph[node[s[i]][0][0]].pb(node[u][j][0]); u = par[par[u][j]][1]; } u = t[i], v = par[LCA][1]; for(int j = 17; j >= 0; j--) { if(in[par[u][j]] <= in[v] && out[par[u][j]] >= out[v]) continue; dirGraph[node[s[i]][0][0]].pb(node[u][j][0]); u = par[par[u][j]][1]; } u = par[t[i]][1], v = par[LCA][1]; for(int j = 17; j >= 0; j--) { if(in[par[u][j]] <= in[v] && out[par[u][j]] >= out[v]) continue; dirGraph[node[u][j][1]].pb(node[s[i]][0][0]); u = par[par[u][j]][1]; } u = s[i], v = par[LCA][1]; for(int j = 17; j >= 0; j--) { if(in[par[u][j]] <= in[v] && out[par[u][j]] >= out[v]) continue; dirGraph[node[u][j][1]].pb(node[s[i]][0][0]); u = par[par[u][j]][1]; } } } // for(int i = 1; i <= nodes; i++) { // debug(i); // for(auto c : dirGraph[i]) // cout << c << " "; // cout << "\n"; // } flag = 0; for(int i = 1; i <= n; i++) { if(vis[node[i][0][0]] == 0) { findCycle(node[i][0][0]); if(flag) break; } } if(flag) cout << "No\n"; else cout << "Yes\n"; } signed main () { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tc; cin >> tc; while(tc--) { init (); solve (); } }
#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...