Submission #1253889

#TimeUsernameProblemLanguageResultExecution timeMemory
1253889ankiteRailway (BOI17_railway)C++20
100 / 100
63 ms25020 KiB
#include <bits/stdc++.h> using namespace std; void print() { cerr << '\n'; } template<typename T, typename... Args> void print(T first, Args... rest) { cerr << first << ' '; print(rest...); } const int li = 2e5 + 5; int n, m, k; vector<pair<int, int>> graph[li]; int tin[li], tout[li], timer = 0, anc[li][20], p_edge[li]; int chosen[li], bit[li]; void dfs(int node = 1, int parent = 0) { tin[node] = ++timer; for (int i = 1; i < 20; i++) anc[node][i] = anc[anc[node][i - 1]][i - 1]; for (pair<int, int> i : graph[node]) { if (i.first != parent) { anc[i.first][0] = node; p_edge[i.first] = i.second; dfs(i.first, node); } } tout[node] = timer; } bool is_ancestor(int a, int b) { return (tin[a] <= tin[b] && tout[a] >= tout[b]); } int lca(int a, int b) { if (is_ancestor(a, b)) return a; for (int i=19; ~i; i--) { if (anc[a][i] && !is_ancestor(anc[a][i], b)) a = anc[a][i]; } return anc[a][0]; } void update(int pos, int val) { for (; pos <= n; pos += (pos & (-pos))) bit[pos] += val; } int query(int a, int b) { int ans = 0; for (; b; b -= (b & (-b))) ans += bit[b]; for (a--; a; a -= (a & (-a))) ans -= bit[a]; return ans; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> k; for (int i=1, a, b; i<=n-1; i++) { cin >> a >> b; graph[a].push_back({b, i}); graph[b].push_back({a, i}); } dfs(); while (m--) { // cout << " *" << m << "\n"; int s, l; cin >> s; for (int i=0; i<s; i++) cin >> chosen[i]; sort(chosen, chosen + s, [](int A, int B) { return tin[A] < tin[B]; }); chosen[s] = chosen[0]; for (int i = 0; i < s; i++) { int l = lca(chosen[i], chosen[i + 1]); update(tin[chosen[i]], 1); update(tin[chosen[i + 1]], 1); update(tin[l], -2); } } vector<int> ans; for (int i=2; i<=n; i++) if (query(tin[i], tout[i]) >= 2 * k) ans.push_back(p_edge[i]); sort(ans.begin(), ans.end()); cout << ans.size() << '\n'; for (int i : ans) cout << i << ' '; 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...