Submission #1299828

#TimeUsernameProblemLanguageResultExecution timeMemory
1299828nekolieRailway (BOI17_railway)C++20
100 / 100
122 ms33948 KiB
#include <bits/stdc++.h> using namespace std; const int M = 100001; int n,m,k,ile[M]; vector<int> odp; vector<pair<int,int>> tree[M]; map<int,int> mp[M]; void dfs(int v, int p, int ind) { for (auto [u,i] : tree[v]) { if (u == p) continue; dfs(u,v,i); if (mp[v].size() < mp[u].size()) swap(mp[v],mp[u]); for (auto it = mp[u].begin(); it != mp[u].end(); it++) { mp[v][it->first] += it->second; if (mp[v][it->first] == ile[it->first]) mp[v].erase(it->first); } mp[u].clear(); } if (mp[v].size() >= k) odp.push_back(ind); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> k; int a,b; for (int i = 1; i < n; i++) cin >> a >> b, tree[a].push_back({b,i}), tree[b].push_back({a,i}); for (int i = 0; i < m; i++) { cin >> ile[i]; for (int j = 0; j < ile[i]; j++) cin >> a, mp[a][i] = 1; } dfs(1,0,0), sort(odp.begin(),odp.end()); cout << odp.size() << endl; for (int i : odp) cout << i << " "; cout << endl; 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...