Submission #243307

#TimeUsernameProblemLanguageResultExecution timeMemory
243307johuthaRailway (BOI17_railway)C++17
100 / 100
265 ms61140 KiB
#include <iostream> #include <vector> #include <algorithm> #include <set> #define int int64_t using namespace std; int log2(int n) { int r = 0; for (; n; n /= 2) r++; return r; } struct tree { int n; vector<vector<int>> adjlist; vector<vector<int>> st; vector<vector<int>> en; vector<int> res; set<int>* smldfs(int curr, int par) { set<int>* rs = new set<int>(st[curr].begin(), st[curr].end()); for (auto next : adjlist[curr]) { if (next == par) continue; set<int>* ot = smldfs(next, curr); if (ot->size() > rs->size()) swap(ot, rs); for (auto i : (*ot)) { rs->insert(i); } } for (auto i : en[curr]) { rs->erase(i); } res[curr] = rs->size(); return rs; } vector<vector<int>> table; vector<int> lvl; int logn; void dfs(int curr, int par, int lv) { lvl[curr] = lv; table[0][curr] = par; for (auto next : adjlist[curr]) if (next != par) dfs(next, curr, lv + 1); } void prelca() { logn = log2(n) + 1; table.resize(logn, vector<int>(n)); lvl.resize(n); dfs(0, -1, 0); table[0][0] = 0; for (int i = 1; i < logn; i++) { for (int j = 0; j < n; j++) { table[i][j] = table[i - 1][table[i - 1][j]]; } } } int lca(int a, int b) { if (lvl[a] < lvl[b]) swap(a, b); int ld = lvl[a] - lvl[b]; for (int j = 0; j < logn; j++) { if (ld & (1<<j)) a = table[j][a]; } if (a == b) return a; for (int j = logn - 1; j >= 0; j--) { if (table[j][a] != table[j][b]) { a = table[j][a]; b = table[j][b]; } } return table[0][a]; } }; signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m, k; cin >> n >> m >> k; tree t; t.n = n; t.adjlist.resize(n); vector<pair<int,int>> edges; for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; a--; b--; edges.emplace_back(a, b); t.adjlist[a].push_back(b); t.adjlist[b].push_back(a); } t.prelca(); t.st.resize(n); t.en.resize(n); for (int i = 0; i < m; i++) { int c; cin >> c; int l = -1; for (int j = 0; j < c; j++) { int a; cin >> a; a--; t.st[a].push_back(i); if (l == -1) l = a; else l = t.lca(l, a); } t.en[l].push_back(i); } t.res.resize(n); t.smldfs(0, -1); vector<int> sol; for (int i = 0; i < n - 1; i++) { auto e = edges[i]; int a = (t.lvl[e.first] > t.lvl[e.second] ? e.first : e.second); if (t.res[a] >= k) sol.push_back(i + 1); } cout << sol.size() << "\n"; for (auto i : sol) cout << i << " "; cout << "\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...