Submission #1265804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265804		canhnam357	Railway (BOI17_railway)	C++20	100 / 100	118 ms	47940 KiB

railway

// source problem : 
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define int long long
#define lb lower_bound
#define ub upper_bound
#define MASK(i) (1LL << (i))
const int inf = 1e18;
void ckmax(int& f, int s)
{
    f = (f > s ? f : s);
}
void ckmin(int& f, int s)
{
    f = (f < s ? f : s);
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<pair<int, int>>> adj(n);
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        adj[--u].emplace_back(--v, i - 1);
        adj[v].emplace_back(u, i - 1);
    }
    vector<vector<int>> q(n);
    vector<int> cnt(m);
    for (int i = 0; i < m; i++)
    {
        int a;
        cin >> a;
        cnt[i] = a;
        while (a--)
        {
            int x;
            cin >> x;
            q[--x].push_back(i);
        }
    }
    vector<int> ans(n - 1);
    function<void(int, int, map<int, int>&)> dfs = [&](int u, int p, map<int, int>& mp)
    {
        for (int i : q[u]) mp[i]++;
        for (auto [v, id] : adj[u])
        {
            if (v == p) continue;
            map<int, int> cmp;
            dfs(v, u, cmp);
            ans[id] += cmp.size();
            if (cmp.size() > mp.size())
            {
                for (auto [f, s] : mp)
                {
                    cmp[f] += s;
                    if (cmp[f] == cnt[f]) cmp.erase(f);
                }
                swap(mp, cmp);
            }
            else
            {
                for (auto [f, s] : cmp)
                {
                    mp[f] += s;
                    if (mp[f] == cnt[f]) mp.erase(f);
                }
            }
        }
    };
    map<int, int> mp;
    dfs(0, -1, mp);
    cout << count_if(all(ans), [&](int i){return i >= k;}) << '\n';
    for (int i = 0; i < n - 1; i++)
    {
        if (ans[i] >= k) cout << i + 1 << ' ';
    }
    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