제출 #934495

#제출 시각아이디문제언어결과실행 시간메모리
934495MisterReaperRailway (BOI17_railway)C++17
36 / 100
88 ms27336 KiB
#include <bits/stdc++.h> using i64 = long long; void solve() { int n, m, k; std::cin >> n >> m >> k; std::vector adj(n, std::vector<std::pair<int, int>> ()); for(int i = 0; i < n - 1; i++) { int u, v; std::cin >> u >> v; adj[--u].emplace_back(--v, i); adj[v].emplace_back(u, i); } const int L = std::__lg(n) + 2; int timer = 0; std::vector par(n, std::vector<int> (L)); std::vector<int> tin(n), tout(n), dep(n), val(n), pedge(n); auto dfs = [&](auto&& self, int node, int p) -> void { tin[node] = timer++; par[node][0] = p; for(auto [child, idx] : adj[node]) { if(child == p) { continue; } pedge[child] = idx; dep[child] = dep[node] + 1; self(self, child, node); } tout[node] = timer++; }; dfs(dfs, 0, 0); for(int lg = 1; lg < L; lg++) { for(int i = 0; i < n; i++) { par[i][lg] = par[par[i][lg - 1]][lg - 1]; } } std::vector s(m, std::vector<int> ()); for(int i = 0; i < m; i++) { int x; std::cin >> x; s[i].resize(x); for(int j = 0; j < x; j++) { std::cin >> s[i][j]; s[i][j]--; } std::sort(s[i].begin(), s[i].end(), [&](int lhs, int rhs) -> bool { return tin[lhs] < tin[rhs]; }); s[i].emplace_back(s[i].front()); } auto get = [&](int node, int l) -> int { for(int lg = L - 1; lg >= 0; lg--) { if(l >> lg & 1) { node = par[node][lg]; } } return node; }; auto lca = [&](int a, int b) -> int { if(dep[b] > dep[a]) { std::swap(a, b); } a = get(a, dep[a] - dep[b]); for(int lg = L - 1; lg >= 0; lg--) { if(par[a][lg] != par[b][lg]) { a = par[a][lg]; b = par[b][lg]; } } return (a == b ? a : par[a][0]); }; for(int i = 0; i < m; i++) { int x = int(s[i].size()); for(int j = 0; j + 1 < x; j++) { int u = s[i][j], v = s[i][j + 1]; int g = lca(u, v); //std::cerr << u << " " << v << " :: " << g << "\n"; val[u]++; val[v]++; val[g] -= 2; } } /* for(int i = 0; i < n; i++) { std::cerr << val[i] << " \n"[i == n - 1]; } */ auto dfs2 = [&](auto&& self, int node, int p) -> void { for(auto [child, idx] : adj[node]) { if(child == p) { continue; } self(self, child, node); val[node] += val[child]; } }; dfs2(dfs2, 0, 0); std::vector<int> ans; for(int i = 0; i < n; i++) { //std::cerr << val[i] << " \n"[i == n - 1]; if(val[i] >= 2 * k) { ans.emplace_back(pedge[i]); } } std::cout << int(ans.size()) << "\n"; for(int i = 0; i < int(ans.size()); i++) { std::cout << ans[i] + 1 << " "; } return; } signed main() { #ifdef LOCAL freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL); int t = 1; //std::cin >> t; for(int i = 1; i <= t; i++) { solve(); } 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...