Submission #1055409

#TimeUsernameProblemLanguageResultExecution timeMemory
1055409BoasJail (JOI22_jail)C++17
0 / 100
18 ms892 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; template <typename T1, typename T2> using indexed_map = tree<T1, T2, less<T1>, rb_tree_tag, tree_order_statistics_node_update>; template <typename T> using indexed_set = indexed_map<T, null_type>; #define loop(x, i) for (int i = 0; i < (x); i++) #define loop1(x, i) for (int i = 1; i <= (x); i++) #define rev(x, i) for (int i = (int)(x) - 1; i >= 0; i--) #define itloop(x) for (auto it = begin(x); x != end(x); it++) #define itrev(x) for (auto it = rbegin(x); x != rend(x); it++) #define int long long #define INF ((int64_t)(4e18 + 1)) #define INF32 ((int32_t)(2e9 + 1)) #define ALL(x) begin(x), end(x) #define RALL(x) rbegin(x), rend(x) #define existsIn(x, l) (count(ALL(l), x) > 0) #define removeIn(x, l) l.erase(find(ALL(l), x)) #define pb push_back #define sz(x) (int)(x).size() #define F first #define S second #define var const auto & #define foreach(l) for (var e : l) typedef pair<int, int> ii; typedef tuple<int, int, int> iii; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<ii> vii; typedef vector<iii> viii; typedef vector<vii> vvii; typedef vector<viii> vviii; typedef set<int> si; typedef set<ii> sii; typedef set<iii> siii; typedef vector<si> vsi; typedef vector<sii> vsii; typedef vector<vsi> vvsi; typedef vector<string> vstr; typedef vector<vector<string>> vvstr; typedef vector<bool> vb; typedef vector<vb> vvb; typedef vi::iterator viit; typedef si::iterator siit; typedef int8_t in8; typedef int16_t in16; typedef int32_t in32; typedef int64_t in64; typedef bitset<500> bs; typedef vector<bs> vbs; typedef vector<vbs> vvbs; void solve() { int n, m; cin >> n; vvi adj(n); loop(n - 1, i) { int a, b; cin >> a >> b; a--; b--; adj[a].pb(b); adj[b].pb(a); } cin >> m; vvbs bedRooms(20, vbs(n)); vvi p(20, vi(n)); vi s(m), t(m), d(n); loop(m, i) { cin >> s[i] >> t[i]; s[i]--; t[i]--; bedRooms[0][s[i]][i] = 1; } auto dfs = [&](auto &&self, int i, int prev) -> void { for (int j : adj[i]) { if (j == prev) continue; d[j] = d[i] + 1; p[0][j] = i; self(self, j, i); } }; dfs(dfs, 0, 0); loop1(19, x) { loop(n, i) { int half = p[x - 1][i]; p[x][i] = p[x - 1][half]; bedRooms[x][i] = bedRooms[x - 1][i] | bedRooms[x - 1][half]; } } typedef pair<int, bs> ibs; auto getParent = [&](int i, int k) -> ibs { bs bedrms; loop(20, x) { if ((1 << x) & k) { bedrms |= bedRooms[x][i]; i = p[x][i]; } } bedrms |= bedRooms[0][i]; return {i, bedrms}; }; auto LCA = [&](int A, int b) -> ibs { if (d[A] - d[b] < 0) swap(A, b); auto [a, bedrms] = getParent(A, d[A] - d[b]); if (a == b) return {a, bedrms}; rev(20, x) { if (p[x][a] != p[x][b]) { bedrms |= bedRooms[x][a]; bedrms |= bedRooms[x][b]; a = p[x][a]; b = p[x][b]; } } bedrms |= bedRooms[1][a]; bedrms |= bedRooms[0][b]; return {p[0][a], bedrms}; }; int done = 0; vvi inPad(m); vi ervoor(m); loop(m, i) { auto [lca, bedrms] = LCA(s[i], t[i]); for (int j = bedrms._Find_first(); j < 500; j = bedrms._Find_next(j)) { if (j == i) continue; ervoor[i]++; inPad[j].pb(i); } } stack<int> q; loop(m, i) { if (ervoor[i] == 0) q.push(i); } while (!q.empty()) { int i = q.top(); q.pop(); done++; for (int j : inPad[i]) { ervoor[j]--; if (ervoor[j] == 0) { q.push(j); } } } if (done == m) cout << "Yes" << endl; else cout << "No" << endl; } signed main() { cin.tie(0)->sync_with_stdio(0); int t = 1; cin >> t; while (t--) { 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...