Submission #549610

#	Time	Username	Problem	Language	Result	Execution time	Memory
549610		Jarif_Rahman	Railway (BOI17_railway)	C++17	100 / 100	214 ms	43424 KiB

railway

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

struct BIT{
    int n;
    vector<ll> sm;
    BIT(){}
    BIT(int _n){
        n = _n;
        sm.resize(n);
    }
    void add(int in, ll x){
        in++;
        while(in <= n) sm[in-1]+=x, in+=in&-in;
    }
    void add(int l, int r, ll x){
        add(l, x);
        if(r+1 < n) add(r+1, -x);
    }
    ll get(int in){
        in++;
        ll s = 0;
        while(in >= 1) s+=sm[in-1], in-=in&-in;
        return s;
    }
};

struct HLD{
    int n;
    vector<vector<int>> v;
    vector<int> sz;
    vector<int> id;
    vector<int> top;
    vector<int> depth;
    vector<int> p;
    vector<int> dfs_array;
    int cnt = 0;

    BIT bit;

    HLD(int _n){
        n = _n;
        v.assign(n, {});
    }

    void pre_dfs(int nd, int ss, int d){
        for(int x: v[nd]) if(x != ss) pre_dfs(x, nd, d+1);
        p[nd] = ss;
        depth[nd] = d;
        for(int x: v[nd]) if(x != ss) sz[nd]+=sz[x];
    }

    void dfs(int nd, int ss, int tp){
        id[nd] = cnt;
        cnt++;
        dfs_array.pb(nd);
        top[nd] = tp;

        int mx = 0, in = -1;
        for(int x: v[nd]) if(x != ss && sz[x] > mx) mx = sz[x], in = x;

        if(in != -1) dfs(in, nd, tp);
        for(int x: v[nd]) if(x != ss && x != in) dfs(x, nd, x);
    }

    void init(){
        sz.assign(n, 1);
        p.assign(n, -1);
        depth.assign(n, -1);
        pre_dfs(0, -1, 0);

        id.assign(n, -1);
        top.assign(n, -1);
        dfs(0, -1, 0);

        bit = BIT(n);
    }

    void upd(vector<int> s){
        priority_queue<tuple<int, int, int>> pq;
        for(int x: s) pq.push({depth[top[x]], top[x], x});
        while(!pq.empty()){
            int tp = top[get<2>(pq.top())];
            int mx = id[get<2>(pq.top())], mn = id[get<2>(pq.top())];
            while(!pq.empty() && get<1>(pq.top()) == tp){
                mx = max(mx, id[get<2>(pq.top())]);
                mn = min(mn, id[get<2>(pq.top())]);
                pq.pop();
            }
            if(pq.empty()){
                if(mn < mx) bit.add(mn+1, mx, 1);
            }
            else{
                bit.add(id[tp], mx, 1);
                pq.push({depth[top[p[tp]]], top[p[tp]], p[tp]});
            }
        }
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m, k; cin >> n >> m >> k;
    map<pair<int, int>, int> mp;
    HLD hld(n);

    for(int i = 1; i < n; i++){
        int a, b; cin >> a >> b; a--, b--;
        if(a > b) swap(a, b);
        mp[{a, b}] = i;
        hld.v[a].pb(b);
        hld.v[b].pb(a);
    }

    hld.init();

    for(int i = 0; i < m; i++){
        int si; cin >> si;
        vector<int> s(si);
        for(int &x: s) cin >> x, x--;
        hld.upd(s);
    }

    vector<int> ans;
    for(int i = 1; i < n; i++){
        if(hld.bit.get(i) >= k){
            int a = hld.dfs_array[i], b = hld.p[a];
            if(a > b) swap(a, b);
            ans.pb(mp[{a, b}]);
        }
    }

    sort(ans.begin(), ans.end());

    cout << ans.size() << "\n";
    for(int x: ans) cout << x << " ";
    cout << "\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