Submission #1281046

#TimeUsernameProblemLanguageResultExecution timeMemory
1281046david_g611Railway (BOI17_railway)C++20
100 / 100
223 ms41356 KiB
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int NMAX=1e5;
int n, m, k, s[NMAX+1], total[NMAX+1];
vector<pair<int, int>> g[NMAX+1];
unordered_map<int, int> freq[NMAX+1];

void dfs(int nod, int par, int index)
{
    //calc muchia par->nod
    for(auto &[key, val]:freq[nod])
        if(val>0 && val<s[key])
            ++total[index];

    for(auto &[to, edge_id]:g[nod])
    {
        if(to==par)continue;
        dfs(to, nod, edge_id);
        if(freq[nod].size() < freq[to].size())
        {
            swap(freq[nod], freq[to]);
            total[index]=total[edge_id];
        }
        for(auto &[key, val]:freq[to])
        {
            if(freq[nod][key]==0 && val>0)++total[index];
            freq[nod][key]+=val;
            if(freq[nod][key]==s[key])--total[index];
        }
    }
}
signed main()
{
    cin>>n>>m>>k;
    for(int i=1, x, y; i<n; i++)
    {
        cin>>x>>y;
        g[x].push_back({y, i});
        g[y].push_back({x, i});
    }
    for(int i=1; i<=m; i++)
    {
        cin>>s[i];
        for(int j=1, p; j<=s[i]; j++)
        {
            cin>>p;
            freq[p][i]++;
        }
    }
    dfs(1, 0, 0);
    vector<int> care;
    for(int i=1; i<n; i++)
        if(total[i]>=k)
            care.push_back(i);
    cout<<care.size()<<'\n';
    sort(care.begin(), care.end());
    for(auto &x:care)cout<<x<<' ';
    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...