제출 #852363

#제출 시각아이디문제언어결과실행 시간메모리
852363EJIC_B_KEDAXJail (JOI22_jail)C++14
5 / 100
5073 ms52468 KiB
#include <bits/stdc++.h> #include <random> #ifndef LOCAL //#pragma GCC optimize("O3") //#pragma GCC optimize("Ofast") //#pragma GCC optimize("unroll-loops") //#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt") #endif using namespace std; typedef long long ll; typedef double dd; typedef long double ld; typedef unsigned int uii; #define x first #define y second #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() void solve(); mt19937_64 mt(1); int32_t main() { #ifdef LOCAL freopen("input.in", "r", stdin); freopen("output.out", "w", stdout); #else ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); //freopen("amusing.in", "r", stdin); //freopen("amusing.out", "w", stdout); #endif cout << fixed << setprecision(30); int tests = 1; cin >> tests; while (tests--) { solve(); } } int tim = 0; bool ans = true; void dfs(int s, int p, vector<vector<int>>& g, vector<int>& tin, vector<int>& tout, vector<int>& pr) { tin[s] = tim++; pr[s] = p; for (int i : g[s]) { if (i != p) { dfs(i, s, g, tin, tout, pr); } } tout[s] = tim++; } void find_cycle(int s, vector<vector<int>>& g, vector<int>& used) { used[s] = 1; for (int i : g[s]) { if (used[i] == 1) { ans = false; } if (!used[i]) { find_cycle(i, g, used); } } used[s] = 2; } bool a_p_b(int a, int b, vector<int>& tin, vector<int>& tout) { return tin[a] <= tin[b] && tout[a] >= tout[b]; } struct path { int u, v; }; void solve() { tim = 0; int n; cin >> n; vector<vector<int>> g(n); for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; v--; u--; g[v].push_back(u); g[u].push_back(v); } vector<int> s(n, -1), t(n, -1), tin(n), tout(n), pr(n), cnt(n, 0); dfs(0, -1, g, tin, tout, pr); int q; cin >> q; ans = true; vector<int> u, used(q, 0); vector<path> z; vector<vector<int>> h(q); for (int i = 0; i < q; i++) { int a, b; cin >> a >> b; a--; b--; s[a] = i; t[b] = i; z.push_back({a, b}); } for (int ii = 0; ii < q; ii++) { int a, b; a = z[ii].u; b = z[ii].v; int a1 = a, b1 = b; while (!a_p_b(a1, b, tin, tout)) { if (s[a1] != -1) { cnt[s[a1]] += 2; u.push_back(s[a1]); } if (t[a1] != -1) { cnt[t[a1]]++; u.push_back(t[a1]); } a1 = pr[a1]; } while (!a_p_b(b1, a, tin, tout)) { if (s[b1] != -1) { cnt[s[b1]] += 2; u.push_back(s[b1]); } if (t[b1] != -1) { cnt[t[b1]]++; u.push_back(t[b1]); } b1 = pr[b1]; } if (s[b1] != -1) { cnt[s[b1]] += 2; u.push_back(s[b1]); } if (t[b1] != -1) { cnt[t[b1]]++; u.push_back(t[b1]); } for (int i : u) { if (!cnt[i]) { continue; } if (cnt[i] == 2) { if (a_p_b(a, z[i].v, tin, tout) ^ a_p_b(a, b, tin, tout)) { cout << "No\n"; return; } } if (cnt[i] == 1) { if (a_p_b(b, z[i].u, tin, tout) ^ a_p_b(b, a, tin, tout)) { cout << "No\n"; return; } } if (cnt[i] > 2 && i != ii) { cout << "No\n"; return; } cnt[i] = 0; } u.clear(); } for (int ii = 0; ii < q; ii++) { int a, b; a = z[ii].u; b = z[ii].v; int a1 = a, b1 = b, cnt1 = 0; do { cnt1++; if (s[a1] != -1) { cnt[s[a1]] += 2; u.push_back(s[a1]); } if (t[a1] != -1) { cnt[t[a1]]++; u.push_back(t[a1]); } a1 = pr[a1]; } while (!a_p_b(a1, b, tin , tout) && cnt1 < 10000); cnt1 = 0; do { cnt1++; if (s[b1] != -1) { cnt[s[b1]] += 2; u.push_back(s[b1]); } if (t[b1] != -1) { cnt[t[b1]]++; u.push_back(t[b1]); } b1 = pr[b1]; } while (!a_p_b(b1, a, tin, tout) && cnt1 < 10000); if (b1 != a) { if (s[b1] != -1) { cnt[s[b1]] += 2; u.push_back(s[b1]); } if (t[b1] != -1) { cnt[t[b1]]++; u.push_back(t[b1]); } } for (int i : u) { if (!cnt[i]) { continue; } if (cnt[i] == 2) { h[ii].push_back(i); } if (cnt[i] == 1) { h[i].push_back(ii); } cnt[i] = 0; } u.clear(); } ans = true; for (int i = 0; i < q; i++) { if (!used[i]) { find_cycle(i, h, used); if (!ans) { cout << "No\n"; return; } } } if (ans) { cout << "Yes\n"; } else { cout << "No\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...