Submission #1322476

#TimeUsernameProblemLanguageResultExecution timeMemory
1322476s0me0neRailway (BOI17_railway)C++20
100 / 100
80 ms25756 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; static const int MAXN = 100'005; int n, m, k; // trying out maxn just to see the speed increase vector<pair<int,int>> adj[MAXN]; int p[20][MAXN], depth[MAXN], tin[MAXN], tout[MAXN], timer, pedge[MAXN]; ll diff[MAXN], ecnt[MAXN]; void dfs(int u, int rt, int pe) { p[0][u] = rt; pedge[u] = pe; tin[u] = ++timer; for (auto [v, id] : adj[u]) { if (v == rt) continue; depth[v] = depth[u] + 1; dfs(v, u, id); } tout[u] = timer; } int lca(int a, int b) { if (depth[a] < depth[b]) swap(a, b); for (int i = 19; i >= 0; i--) if (p[i][a] && depth[p[i][a]] >= depth[b]) a = p[i][a]; if (a == b) return a; for (int i = 19; i >= 0; i--) if (p[i][a] && p[i][a] != p[i][b]) { a = p[i][a]; b = p[i][b]; } return p[0][a]; } void dfs2(int u, int rt) { for (auto [v, id] : adj[u]) { if (v == rt) continue; dfs2(v, u); diff[u] += diff[v]; ecnt[id] = diff[v]; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m >> k; for (int i = 1; i <= n - 1; i++) { int a, b; cin >> a >> b; adj[a].push_back({b, i}); adj[b].push_back({a, i}); } dfs(1, 0, 0); for (int i = 1; i < 20; i++) for (int v = 1; v <= n; v++) p[i][v] = p[i - 1][p[i - 1][v]]; while (m--) { int s; cin >> s; vector<int> nodes(s); for (int i = 0; i < s; i++) cin >> nodes[i]; sort(nodes.begin(), nodes.end(), [&](int a, int b) { return tin[a] < tin[b]; }); vector<int> vt = nodes; for (int i = 0; i + 1 < nodes.size(); i++) vt.push_back(lca(nodes[i], nodes[i + 1])); sort(vt.begin(), vt.end(), [&](int a, int b) { return tin[a] < tin[b]; }); vt.erase(unique(vt.begin(), vt.end()), vt.end()); stack<int> st; st.push(vt[0]); for (int i = 1; i < vt.size(); i++) { int u = vt[i]; while (!st.empty() && !(tin[st.top()] <= tin[u] && tin[u] <= tout[st.top()])) st.pop(); int v = st.top(), w = lca(u, v); diff[u]++; diff[v]++; diff[w] -= 2; st.push(u); } } dfs2(1, 0); vector<int> ans; for (int i = 1; i <= n - 1; i++) if (ecnt[i] >= k) ans.push_back(i); cout << ans.size() << '\n'; for (int x : ans) cout << x << ' '; cout << '\n'; 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...