Submission #997252

#TimeUsernameProblemLanguageResultExecution timeMemory
997252vladiliusJail (JOI22_jail)C++17
5 / 100
108 ms46420 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<int, int>; #define pb push_back #define ff first #define ss second #define ins insert struct FT{ vector<int> bit; int n; FT(int ns){ n = ns; bit.resize(n + 1); } void add(int v, int k){ while (v <= n){ bit[v] += k; v |= (v + 1); } } void upd(int l, int r, int x){ add(l, x); add(r + 1, -x); } int get(int v){ int out = 0; while (v > 0){ out += bit[v]; v = (v & (v + 1)) - 1; } return out; } }; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tt; cin>>tt; while (tt--){ int n; cin>>n; vector<int> g[n + 1]; for (int i = 1; i < n; i++){ int a, b; cin>>a>>b; g[a].pb(b); g[b].pb(a); } const int lg = log2(n); vector<vector<int>> pw(n + 1, vector<int>(lg + 1)); vector<int> tin(n + 1), tout(n + 1); int timer = 0; function<void(int, int)> fill = [&](int v, int pr){ tin[v] = ++timer; pw[v][0] = pr; for (int i = 1; i <= lg; i++){ pw[v][i] = pw[pw[v][i - 1]][i - 1]; } for (int i: g[v]){ if (i == pr) continue; fill(i, v); } tout[v] = timer; }; fill(1, 1); auto check = [&](int x, int y){ return (tin[x] <= tin[y] && tout[x] >= tout[y]); }; int m; cin>>m; vector<int> s(m + 1), t(m + 1); for (int i = 1; i <= m; i++){ cin>>s[i]>>t[i]; } auto lca = [&](int x, int y){ if (check(x, y)) return x; if (check(y, x)) return y; for (int i = lg; i >= 0; i--){ if (!check(pw[x][i], y)){ x = pw[x][i]; } } return pw[x][0]; }; vector<int> p1(n + 1), p2(n + 1); for (int i = 1; i <= n; i++){ p1[i] = p2[i] = i; } vector<int> w1(n + 1), w2(n + 1); for (int i = 1; i <= m; i++){ w1[s[i]] = w2[t[i]] = i; } pw[1][0] = 0; function<int(int)> move1 = [&](int v){ if (w1[v] || !v) return v; if (p1[v] == v){ p1[v] = pw[v][0]; } return p1[v] = move1(p1[v]); }; function<int(int)> move2 = [&](int v){ if (w2[v] || !v) return v; if (p2[v] == v){ p2[v] = pw[v][0]; } return p2[v] = move2(p2[v]); }; vector<int> f[m + 1]; function<void(int)> dfs1 = [&](int v){ w1[s[v]] = 0; int l = lca(s[v], t[v]), x; while (check(l, x = move1(s[v]))){ f[v].pb(w1[x]); dfs1(w1[x]); } while (check(l, x = move1(t[v]))){ f[v].pb(w1[x]); dfs1(w1[x]); } }; function<void(int)> dfs2 = [&](int v){ w2[t[v]] = 0; int l = lca(s[v], t[v]), x; while (check(l, x = move2(s[v]))){ f[w2[x]].pb(v); dfs2(w2[x]); } while (check(l, x = move2(t[v]))){ f[w2[x]].pb(v); dfs2(w2[x]); } }; for (int i = 1; i <= m; i++){ if (w1[s[i]]){ dfs1(i); } } for (int i = 1; i <= m; i++){ if (w2[t[i]]){ dfs2(i); } } vector<bool> used(m + 1), seen(m + 1); vector<int> order; bool out = 1; function<void(int)> dfs = [&](int v){ if (!out) return; used[v] = seen[v] = 1; for (int i: f[v]){ if (used[i]){ if (seen[i]){ out = 0; return; } continue; } dfs(i); } order.pb(v); seen[v] = 0; }; for (int i = 1; i <= m; i++){ if (!used[i]){ dfs(i); } } if (!out){ cout<<"No"<<"\n"; continue; } vector<int> a(n + 1); FT T(n); auto upd = [&](int v, int k){ a[v] += k; T.upd(tin[v], tout[v], k); }; for (int i = 1; i <= m; i++){ upd(s[i], 1); } auto get = [&](int x, int y){ int l = lca(x, y); return T.get(tin[x]) + T.get(tin[y]) - 2 * T.get(tin[l]) + a[l]; }; for (int i: order){ if (get(s[i], t[i]) > 1){ out = 0; break; } upd(s[i], -1); upd(t[i], 1); } cout<<((out) ? "Yes" : "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...