Submission #1233557

#TimeUsernameProblemLanguageResultExecution timeMemory
1233557chikien2009Railway (BOI17_railway)C++20
100 / 100
118 ms42824 KiB
#include <bits/stdc++.h> using namespace std; void setup() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } int n, m, k, a, b, sz[100000]; vector<pair<int, int>> g[100000]; vector<int> res, s[100000]; inline map<int, int> DFS(int node, int par, int last) { map<int, int> cur, temp; for (auto & i : s[node]) { cur[i]++; } for (auto & i : g[node]) { if (i.first != par) { temp = DFS(i.first, node, i.second); if (temp.size() > cur.size()) { swap(cur, temp); } for (auto & j : temp) { if (j.second + cur[j.first] == sz[j.first]) { cur.erase(j.first); } else { cur[j.first] += j.second; } } } } if (cur.size() >= k) { res.push_back(last); } return cur; } int main() { setup(); cin >> n >> m >> k; for (int i = 0; i < n - 1; ++i) { cin >> a >> b; g[a - 1].push_back({b - 1, i + 1}); g[b - 1].push_back({a - 1, i + 1}); } for (int i = 0; i < m; ++i) { cin >> sz[i]; for (int j = 0; j < sz[i]; ++j) { cin >> a; s[a - 1].push_back(i); } } DFS(0, 0, 0); cout << res.size() << "\n"; sort(res.begin(), res.end()); for (auto & i : res) { 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...