Submission #937058

#TimeUsernameProblemLanguageResultExecution timeMemory
937058PanndaJail (JOI22_jail)C++17
100 / 100
1589 ms341212 KiB
#include <bits/stdc++.h> using namespace std; struct Tree { int log, idx; vector<int> depth; vector<vector<int>> lift; vector<vector<int>> f; vector<array<int, 2>> edges; Tree(int n, vector<vector<int>> &adj, int root = 0) : log(32 - __builtin_clz(n)), idx(0), depth(n), lift(n, vector<int>(log, -1)), f(n, vector<int>(log, -1)) { auto dfs = [&](auto self, int u, int p) -> void { for (int v : adj[u]) { if (v == p) continue; depth[v] = depth[u] + 1; lift[v][0] = u; f[v][0] = idx++; for (int i = 1; i < log; i++) { int w = lift[v][i - 1]; if (w != -1) { lift[v][i] = lift[w][i - 1]; if (f[w][i - 1] != -1) f[v][i] = idx++; if (f[w][i - 1] != -1) edges.push_back({f[v][i], f[v][i - 1]}); if (f[w][i - 1] != -1) edges.push_back({f[v][i], f[w][i - 1]}); } } self(self, v, u); } }; depth[root] = 0; f[root][0] = idx++; dfs(dfs, root, -1); } int count() { return idx; } vector<array<int, 2>> getEdges() { return edges; } int lca(int u, int v) { if (depth[u] > depth[v]) swap(u, v); for (int i = log - 1; i >= 0; i--) { int w = lift[v][i]; if (w != -1 && depth[w] >= depth[u]) v = w; } if (u == v) return u; for (int i = log - 1; i >= 0; i--) { if (lift[u][i] != lift[v][i]) { u = lift[u][i]; v = lift[v][i]; } } return lift[u][0]; } int getIntermediate(int s, int t) { // not to take s == t int m = lca(s, t); if (s != m) return lift[s][0]; for (int i = log - 1; i >= 0; i--) { int w = lift[t][i]; if (w != -1 && depth[w] > depth[s]) t = w; } return t; } int getNode(int u) { return f[u][0]; } vector<int> getPath(int u, int v) { vector<int> res; if (depth[u] > depth[v]) swap(u, v); for (int i = log - 1; i >= 0; i--) { int w = lift[v][i]; if (w != -1 && depth[w] >= depth[u]) { res.push_back(f[v][i]); v = w; } } if (u == v) { res.push_back(f[u][0]); return res; } for (int i = log - 1; i >= 0; i--) { if (lift[u][i] != lift[v][i]) { res.push_back(f[u][i]); res.push_back(f[v][i]); u = lift[u][i]; v = lift[v][i]; } } res.push_back(f[u][1]); res.push_back(f[v][0]); return res; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { int n; cin >> n; vector<vector<int>> adj(n); for (int i = 0; i < n - 1; i++) { int u, v; cin >> u >> v; u--; v--; adj[u].push_back(v); adj[v].push_back(u); } int m; cin >> m; Tree tree(n, adj); vector<vector<int>> dag(2 * tree.count() + m); for (auto [u, v] : tree.getEdges()) { dag[v].push_back(u); dag[tree.count() + u].push_back(tree.count() + v); } for (int i = 0; i < m; i++) { int s, t; cin >> s >> t; s--; t--; int u = 2 * tree.count() + i; dag[u].push_back(tree.getNode(s)); dag[u].push_back(tree.count() + tree.getNode(s)); dag[tree.getNode(t)].push_back(u); dag[tree.count() + tree.getNode(t)].push_back(u); s = tree.getIntermediate(s, t); if (s == t) continue; t = tree.getIntermediate(t, s); vector<int> path = tree.getPath(s, t); for (int v : path) { dag[v].push_back(u); dag[u].push_back(tree.count() + v); } } vector<int> deg(2 * tree.count() + m, 0); for (int u = 0; u < 2 * tree.count() + m; u++) { for (int v : dag[u]) { deg[v]++; } } vector<int> que; for (int u = 0; u < 2 * tree.count() + m; u++) { if (!deg[u]) { que.push_back(u); } } for (int i = 0; i < que.size(); i++) { int u = que[i]; for (int v : dag[u]) { if (!--deg[v]) { que.push_back(v); } } } que.size() == 2 * tree.count() + m ? cout << "Yes\n" : cout << "No\n"; } }

Compilation message (stderr)

jail.cpp: In function 'int main()':
jail.cpp:165:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |         for (int i = 0; i < que.size(); i++) {
      |                         ~~^~~~~~~~~~~~
jail.cpp:174:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  174 |         que.size() == 2 * tree.count() + m ? cout << "Yes\n" : cout << "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...