Submission #1053632

#TimeUsernameProblemLanguageResultExecution timeMemory
1053632j_vdd16Jail (JOI22_jail)C++17
0 / 100
5073 ms32020 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 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; 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]; } } if (a == b) return 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]; } return lift[0][a]; } bool isOnSimplePath(int node, int a, int b) { int lca = getLCA(a, b); bool result = isBetween(node, lca, a) || isBetween(node, lca, b); return result; } 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 8 1 2 2 3 3 4 4 5 5 6 6 7 7 8 2 1 5 5 3 1 4 1 2 1 3 1 4 3 2 3 3 4 4 2 1 7 1 2 2 3 2 4 1 5 5 6 5 7 2 7 3 4 6 */ 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; for (int pow = 1; pow < POW; pow++) { loop(j, n) { int next = lift[pow - 1][j]; lift[pow][j] = lift[pow - 1][next]; } } vii routes; cin >> m; loop(i, m) { int s, t; cin >> s >> t; s--; t--; routes.push_back({s, t}); } sort(all(routes)); bool containSuccess = true; vi inDegree(m); vector<set<int>> out(m); loop(i, m) { auto [s1, t1] = routes[i]; loop(j, m) { auto [s2, t2] = routes[j]; if (i == j) continue; //if (s1 < s2 && t1 > t2) containSuccess = false; //if (min(s1, t1) <= min(s2, t2) && max(s2, t2) <= max(s1, t1)) containSuccess = false; //if (min(s1, t1) <= t2 && t2 <= max(s1, t1) && min(s2, t2) <= t1 && t1 <= max(s2, t2)) containSuccess = false; if (isOnSimplePath(t2, s1, t1)) { if (!out[i].count(j)) { out[i].insert(j); inDegree[j]++; } if (isOnSimplePath(s2, s1, t1)) containSuccess = false; } if (isOnSimplePath(s2, s1, t1)) { if (!out[j].count(i)) { out[j].insert(i); inDegree[i]++; } } //if (isOnSimplePath(s1, s2, t2) && isOnSimplePath(t1, s2, t2)) containSuccess = false; } } stack<int> startingPoints; loop(i, m) { if (inDegree[i] == 0) startingPoints.push(i); } int count = 0; vb vis(m); while (startingPoints.size()) { int node = startingPoints.top(); startingPoints.pop(); if (vis[node]) continue; vis[node] = true; count++; for (int child : out[node]) { inDegree[child]--; if (inDegree[child] == 0) startingPoints.push(child); } } bool testSuccess = true; int prev = 0; for (auto [s, t] : routes) { if (t < prev) { testSuccess = false; } prev = t; } if (testSuccess) { cerr << "Yes (first subtask only)" << endl; } else { cerr << "No (first subtask only)" << 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...