Submission #1281046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281046		david_g611	Railway (BOI17_railway)	C++20	100 / 100	223 ms	41356 KiB

railway

#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;
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 7 / 7
• Subtask 4: 29 / 29
• Subtask 5: 16 / 16
• Subtask 6: 25 / 25