Submission #1053577

#TimeUsernameProblemLanguageResultExecution timeMemory
1053577j_vdd16Jail (JOI22_jail)C++17
0 / 100
12 ms348 KiB
#include <algorithm> #include <bitset> #include <cstdint> #include <cstring> #include <iostream> #include <limits.h> #include <math.h> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <vector> //#define int long long #define loop(X, N) for(int X = 0; X < (N); X++) #define all(V) V.begin(), V.end() #define rall(V) V.rbegin(), V.rend() using namespace std; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<vector<ii>> vvii; typedef vector<bool> vb; typedef vector<vector<bool>> vvb; typedef uint64_t u64; typedef int64_t i64; int n, m; vvi adj; vi depth; vi parent; vii inOut; int counter; void dfs(int node, int p, int d) { depth[node] = d; inOut[node].first = counter++; for (int child : adj[node]) { if (child == p) continue; parent[child] = node; dfs(child, node, d + 1); } inOut[node].second = counter++; } constexpr int POW = 20; vi lift[POW]; bool isAncestor(int a, int b) { return inOut[a].first <= inOut[b].first && inOut[b].first <= inOut[a].second; } bool isBetween(int node, int a, int b) { return isAncestor(a, node) && isAncestor(node, b); } int getLCA(int a, int b) { if (depth[a] < depth[b]) swap(a, b); int todo = depth[a] - depth[b]; loop(pow, POW) { if (todo & (1 << pow)) { a = lift[pow][a]; } } for (int pow = POW - 1; pow >= 0; pow--) { if (lift[pow][a] == lift[pow][a]) continue; a = lift[pow][a]; b = lift[pow][b]; } if (a != b) { a = lift[0][b]; } return a; } bool isOnSimplePath(int node, int a, int b) { int lca = getLCA(a, b); return isBetween(node, lca, a) || isBetween(node, lca, b); } signed main() { ios::sync_with_stdio(0); cin.tie(0); /* 1 7 1 2 2 3 3 4 4 5 5 6 6 7 3 1 3 4 2 2 5 */ /* 1 8 1 2 2 3 3 4 4 5 5 6 6 7 7 8 2 1 5 2 3 */ int q; cin >> q; while (q--) { cin >> n; counter = 0; adj = vvi(n); depth = vi(n); parent = vi(n); inOut = vii(n); loop(i, n - 1) { int a, b; cin >> a >> b; a--; b--; adj[a].push_back(b); adj[b].push_back(a); } dfs(0, -1, 0); loop(i, POW) { lift[i] = vi(n); } loop(i, n) lift[0][i] = parent[i]; lift[0][0] = 0; vii routes; cin >> m; loop(i, m) { int s, t; cin >> s >> t; s--; t--; routes.push_back({s, t}); } for (int pow = 1; pow < POW; pow++) { loop(j, n) { int next = lift[pow - 1][j]; lift[pow][j] = lift[pow - 1][next]; } } bool containSuccess = true; vi inDegree(m); vvi out(m); loop(i, m) { auto [s1, t1] = routes[i]; loop(j, m) { if (i == j) continue; auto [s2, t2] = routes[j]; if (isOnSimplePath(t2, s1, t1)) { out[j].push_back(i); inDegree[i]++; if (isOnSimplePath(s2, s1, t1)) containSuccess = false; } if (isOnSimplePath(t1, s2, t2)) { out[i].push_back(j); inDegree[j]++; if (isOnSimplePath(s1, s2, t2)) containSuccess = false; } } } stack<int> startingPoints; loop(i, m) { if (inDegree[i] == 0) startingPoints.push(i); } int count = 0; while (startingPoints.size()) { int node = startingPoints.top(); startingPoints.pop(); count++; for (int child : out[node]) { inDegree[child]--; if (inDegree[child] == 0) startingPoints.push(child); } } bool success = true; sort(all(routes)); int prev = 0; for (auto [s, t] : routes) { if (t < prev) { success = false; } prev = t; } if (success) { cerr << "Yes" << endl; } else { cerr << "No" << endl; } if (!containSuccess || count != m) { cout << "No" << endl; } else { cout << "Yes" << endl; } } 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...