제출 #1170383

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170383		Nelt	Railway (BOI17_railway)	C++20	100 / 100	65 ms	26028 KiB

railway

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"
using namespace std;
using namespace __gnu_pbds;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T, typename key = less<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
struct SegTree
{
    ll n;
    vector<ll> st;
    SegTree(ll sz = 0)
    {
        n = sz;
        st.resize(n << 1, 0);
    }
    void set(ll i, ll val)
    {
        st[i + n - 1] = val;
    }
    void build()
    {
        for (ll i = n - 1; i >= 1; i--)
            st[i] = st[i << 1] + st[i << 1 | 1];
    }
    void modify(ll p, ll val)
    {
        for (st[p += n - 1] += val; p > 1; p >>= 1)
            st[p >> 1] = st[p] + st[p ^ 1];
    }
    ll query(ll l, ll r)
    {
        ll ans = 0;
        for (l += n - 1, r += n; l < r; l >>= 1, r >>= 1)
        {
            if (l & 1)
                ans += st[l++];
            if (r & 1)
                ans += st[--r];
        }
        return ans;
    }
};
const ll N = 1e5 + 5;
vector<pair<ll, ll>> g[N];
ll ind[N], d[N], f[N], timer = 0, cnt[N];
pair<ll, ll> reald[N];
void dfs(ll v, ll par = 0)
{
    d[v] = ++timer;
    for (auto [to, id] : g[v])
        if (to != par)
            ind[to] = id, dfs(to, v);
    f[v] = timer;
    reald[d[v]] = make_pair(f[v], v);
}
void solve()
{
    ll n, m, k;
    cin >> n >> m >> k;
    k = m - k;
    for (ll i = 1; i < n; i++)
    {
        ll a, b;
        cin >> a >> b;
        g[a].push_back(make_pair(b, i));
        g[b].push_back(make_pair(a, i));
    }
    dfs(1);
    vector<pair<ll, ll>> segs, seg1;
    while (m--)
    {
        ll sz;
        cin >> sz;
        vector<ll> v(sz);
        for (ll &i : v)
            cin >> i, i = d[i];
        sort(v.begin(), v.end());
        ll last = 0;
        for (ll i = 0; i < v.size(); i++)
        {
            if (last + 1 <= v[i] - 1)
            segs.push_back(make_pair(last + 1, v[i] - 1));
            last = v[i];
        }
        if (last + 1 <= n)
            segs.push_back(make_pair(last + 1, n));
        seg1.push_back(make_pair(v.front(), v.back()));
    }
    sort(segs.begin(), segs.end());
    sort(seg1.begin(), seg1.end(), greater());
    ll ptr = 0;
    SegTree st(n);
    for (ll i = 1; i <= n; i++)
    {
        while (ptr < segs.size() and segs[ptr].first <= i)
            st.modify(segs[ptr].second, 1), ptr++;
        cnt[reald[i].second] += st.query(reald[i].first, n);
        // for (auto [l, r] : segs) cnt[reald[i].second] += l <= i and reald[i].first <= r;
    }
    st = SegTree(n);
    ptr = 0;
    for (ll i = n; i >= 1; i--)
    {
        while (ptr < seg1.size() and seg1[ptr].first >= i)
            st.modify(seg1[ptr].second, 1), ptr++;
        cnt[reald[i].second] += st.query(1, reald[i].first);
        // for (auto [l, r] : seg1) cnt[reald[i].second] += i <= l and r <= reald[i].first;
    }
    // for (ll i = 1; i <= n; i++) cout << d[i] << " " << f[i] << endl;
    vector<ll> ans;
    for (ll i = 2; i <= n; i++)
        if (cnt[i] <= k)
            ans.push_back(ind[i]);
    sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for (ll i : ans)
        cout << i << " ";
    cout << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // precomp();
    // cin >> t;
    for (ll cs = 1; cs <= t; cs++)
        solve();
    // cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

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