Submission #1233556

#TimeUsernameProblemLanguageResultExecution timeMemory
1233556chikien2009Railway (BOI17_railway)C++20
0 / 100
81 ms40896 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] = 1; } 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 && node != 0) { 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); 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...