Submission #1168001

#TimeUsernameProblemLanguageResultExecution timeMemory
1168001aycnlJail (JOI22_jail)C++20
0 / 100
6 ms3144 KiB
#include <bits/stdc++.h> using namespace std; #define ii pair <int, int> #define ff first #define ss second #define bit(i) (1 << (i)) #define fto(i, a, b) for (int i = (a); i <= (b); ++i) #define fdto(i, a, b) for (int i = (a); i >= (b); --i) #define flto(i, a, b) for (int i = (a); (1 << i) <= (b); ++i) #define pb push_back #define pf push_front #define endl "\n" #define oo (int)(1e9 + 7) #define maxN 120005 #define l(s) s.length() #define vi vector <int> #define vii vector <ii> #define fat(x, y) for (auto x : y) #define fit(x, y) for (int x : y) #define fiit(x, y) for (ii x : y) #define EPS 1e-9 #define pi (acos(-1)) #define ll long long int n, m; vi ke[maxN], topo; int s[maxN], t[maxN]; int par[maxN], h[maxN]; int p[maxN], pos[maxN], vst[maxN]; void pre_dfs(int u) { for (int v : ke[u]) if (v != par[u]) { par[v] = u; h[v] = h[u] + 1; pre_dfs(v); } } int fSet(int u) { return p[u] == 0 ? u : p[u] = fSet(p[u]); } void uSet(int u, int v) { u = fSet(u); v = fSet(v); if (u == v) return; p[v] = u; } void dfs(int u) { vst[u] = 1; int a = fSet(s[u]), b = fSet(t[u]); while (a != b) { if (h[a] < h[b]) swap(a, b); uSet(par[a], a); if (pos[a] != 0 && pos[a] != u && !vst[pos[a]]) dfs(pos[a]); if (pos[par[a]] != 0 && pos[par[a]] != u && !vst[pos[par[a]]]) dfs(pos[par[a]]); a = fSet(a); } topo.pb(u); } void solve() { cin >> n; fto(i, 1, n) ke[i].clear(), pos[i] = 0, p[i] = 0, par[i] = 0, h[i] = 0; topo.clear(); fto(i, 1, n-1) { int u, v; cin >> u >> v; ke[u].pb(v); ke[v].pb(u); } pre_dfs(1); cin >> m; fto(i, 1, m) { cin >> s[i] >> t[i]; pos[s[i]] = i; vst[i] = 0; } fto(i, 1, m) if (!vst[i]) dfs(i); fto(i, 1, n) p[i] = 0; fto(i, 1, m) vst[i] = 1; for (int u : topo) { vst[u] = u; //cout << u << " "; } //cout << endl; for (int u : topo) { vst[u] = 0; int a = fSet(s[u]), b = fSet(t[u]); while (a != b) { if (h[a] < h[b]) swap(a, b); uSet(par[a], a); //a = fSet(a); if (pos[a] != 0 && pos[a] != u && vst[pos[a]]) { cout << "No" << endl; return; } if (pos[par[a]] != 0 && pos[par[a]] != u && vst[pos[par[a]]]) { cout << "No" << endl; return; } a = fSet(a); } } cout << "Yes" << endl; //for (int u : topo) cout << u << " "; cout << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int test; cin >> test; while (test--) solve(); 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...