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...