Submission #986522

#TimeUsernameProblemLanguageResultExecution timeMemory
986522ShaShiJail (JOI22_jail)C++17
72 / 100
2659 ms1048576 KiB
#include <bits/stdc++.h> #define int long long #define pii pair<int, int> #define all(x) x.begin(), x.end() #define pb push_back #define mp make_pair #define F first #define S second #define kill(x) cout << x << endl, exit(0); #define endl "\n" using namespace std; typedef long long ll; typedef long double ld; const int MAXN = (int)1e6 + 7; const int MOD = 998244853; const ll INF = (ll)1e18 + 7; int t, n, m, q, tmp, tmp2, tmp3, tmp4, ans, k, u, v, w, flag, N, M; int arr[MAXN], h[MAXN], st[MAXN], fn[MAXN], ind[MAXN], par[MAXN]; bool seen[MAXN]; vector<int> adj[MAXN], G[MAXN], ord, Ss[MAXN], T[MAXN]; vector<pii> edge; void DFSsz(int v) { seen[v] = 1; for (int u:adj[v]) { if (seen[u]) continue; h[u] = h[v]+1; par[u] = v; DFSsz(u); } } inline void add_edge(int u, int v) { if (u == v) return; G[u].pb(v); edge.pb(mp(u, v)); } inline void check(int ind, int v) { for (int x:Ss[v]) add_edge(x, ind); for (int x:T[v]) add_edge(ind, x); } inline void process(int ind, int u, int v) { if (h[u] > h[v]) swap(u, v); while (h[v] > h[u]) { check(ind, v); v = par[v]; } while (u != v) { check(ind, u); check(ind, v); u = par[u]; v = par[v]; } check(ind, u); } void DFS(int v) { seen[v] = 1; for (int u:G[v]) if (!seen[u]) DFS(u); ord.pb(v); } void solve() { cin >> n; for (int i=0; i<n+7; i++) adj[i].clear(), G[i].clear(), Ss[i].clear(), T[i].clear(); edge.clear(); ord.clear(); fill(seen, seen+n+7, 0); fill(h, h+n+7, 0); fill(ind, ind+n+7, 0); fill(par, par+n+7, 0); for (int i=1; i<n; i++) { cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } DFSsz(1); cin >> m; for (int i=1; i<=m; i++) { cin >> st[i] >> fn[i]; Ss[st[i]].pb(i); T[fn[i]].pb(i); } for (int i=1; i<=m; i++) process(i, st[i], fn[i]); ord.clear(); fill(seen, seen+n+1, 0); for (int i=1; i<=m; i++) if (!seen[i]) DFS(i); for (int i=0; i<m; i++) ind[ord[i]] = i; for (auto cur:edge) { if (ind[cur.F] < ind[cur.S]) { cout << "No\n"; return; } } cout << "Yes\n"; } int32_t main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> t; while (t--) 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...