Submission #654609

#	Time	Username	Problem	Language	Result	Execution time	Memory
654609		esomer	Railway (BOI17_railway)	C++17	100 / 100	389 ms	57852 KiB

railway

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define endl "\n"

const int MOD = 998244353;

struct segTree {
    int size;
    vector<pair<ll, int>> minimum;
    void init(int n){
        size = 1;
        while (size < n) size *= 2;
        minimum.assign(2 * size, {1e18, 1});
    }

    void build(vector<int> &a, int x, int lx, int rx){
        if (rx - lx == 1){
            if (lx < (int)a.size()){
                minimum[x] = {a[lx], lx};
            }
            return;
        }
        int m = (lx + rx) / 2;
        build(a, 2 * x + 1, lx, m);
        build(a, 2 * x + 2, m, rx);
        minimum[x] = min(minimum[2 * x + 1], minimum[2 * x + 2]);
    }
    void build(vector<int>& a){
        build(a, 0, 0, size);
    }

    pair<ll, int> calc(int l, int r, int x, int lx, int rx){
        if (lx >= r || l >= rx)
            return {1e18, 1};
        if (lx >= l && rx <= r){
            return minimum[x];
        }
        int m = (lx + rx) / 2;
        pair<ll, int> s1 = calc(l, r, 2 * x + 1, lx, m);
        pair<ll, int> s2 = calc(l, r, 2 * x + 2, m, rx);
        return min(s1, s2);
    }

    ll calc(int l, int r){
        return calc(l, r, 0, 0, size).second;
    }
};

struct segTree2{
    int size;
    vector<ll> sums;
    void init(int n){
        size = 1;
        while (size < n) size *= 2;
        sums.assign(2 * size, 0LL);
    }
    void set(int i, int v, int x, int lx, int rx){
        if (rx - lx == 1){
            sums[x] += v;
            return;
        }
        int m = (lx + rx) / 2;
        if (i < m){
            set(i, v, 2 * x + 1, lx, m);
        }else{
            set(i, v, 2 * x + 2, m, rx);
        }
        sums[x] = sums[2 * x + 1] + sums[2 * x + 2];
    }
    void set(int i, int v){
        set (i, v, 0, 0, size);
    }

    ll sum(int l, int r, int x, int lx, int rx){
        if (lx >= r || l >= rx){
            return 0;
        }
        if (lx >= l && rx <= r){
            return sums[x];
        }
        int m = (lx + rx) / 2;
        ll s1 = sum(l, r, 2 * x + 1, lx, m);
        ll s2 = sum(l, r, 2 * x + 2, m, rx);
        return s1 + s2;
    }

    ll sum (int l, int r){
        return sum(l, r, 0, 0, size);
    }
};


int cnt = 0;

void build_euler(int x, vector<vector<pair<int, int>>>& adj, vector<int>& depths, vector<int>& euler_depth, vector<int>& euler, vector<pair<int, int>>& t, vector<pair<int, int>>& t2, vector<int>& pos, vector<int>& id, int p, int edge){
    t[x].first = (int)euler.size();
    t2[x].first = cnt; pos[cnt] = x; cnt++;
    id[x] = edge;
    euler.push_back(x); euler_depth.push_back(depths[x]);
    for(auto pr : adj[x]){
        int node = pr.first;
        if(node == p) continue;
        depths[node] = depths[x] + 1;
        build_euler(node, adj, depths, euler_depth, euler, t, t2, pos, id, x, pr.second);
        t[x].second = (int)euler.size();
        euler.push_back(x); euler_depth.push_back(depths[x]);
    }
    if(t[x].first + 1 == (int)euler.size()){
        t[x].second = (int)euler.size();
        euler.push_back(x); euler_depth.push_back(depths[x]);
    }
    t2[x].second = cnt; pos[cnt] = x; cnt++;
}

void solve(){
    int n, m, k; cin >> n >> m >> k;
    vector<vector<pair<int, int>>> adj(n);
    for(int i = 0; i < n - 1; i++){
        int a, b; cin >> a >> b; a--; b--;
        adj[a].push_back({b, i + 1}); adj[b].push_back({a, i + 1});
    }
    vector<int> depths(n, 0);
    vector<int> euler_depth;
    vector<int> euler;
    vector<int> id(n);
    vector<pair<int, int>> t(n);
    vector<pair<int, int>> t2(n);
    vector<int> pos(2 * n);
    build_euler(0, adj, depths, euler_depth, euler, t, t2, pos, id, -1, -1);
    segTree lca;
    lca.init((int)euler.size()); lca.build(euler_depth);
    vector<int> lc(m);
    vector<vector<int>> mn(n);
    segTree2 lcas; lcas.init(2 * n);
    for(int q = 0; q < m; q++){
        int s; cin >> s;
        vector<int> v(s); for(auto &i : v) cin >> i; for(int i = 0; i < s; i++) v[i]--;
        int l = v[0];
        mn[v[0]].push_back(q);
        set<int> done; done.insert(v[0]);
        for(int i = 1; i < s; i++){
            bool good = done.count(v[i]);
            if(good) continue;
            done.insert(v[i]);
            mn[v[i]].push_back(q);
            l = euler[lca.calc(min(t[l].first, t[v[i]].first), max(t[l].second, t[v[i]].second))];
        }
        lc[q] = l;
        lcas.set(t2[l].first, 1);
    }
    //I have to do one Euler for the different ministers in the subtree.
    //Another one for the LCAs in my subtree, and substract.
    segTree2 ministers; ministers.init(2 * n);
    vector<int> lst(m, -1);
    vector<vector<int>> next(2 * n);
    for(int i = 0; i < 2 * n; i++){
        for(int x : mn[pos[i]]){
            if(lst[x] == -1) {lst[x] = i; ministers.set(i, 1);}
            else {next[lst[x]].push_back(i); lst[x] = i;}
        }
    }
    vector<pair<int, int>> queries(n);
    for(int i = 0; i < n; i++) queries[i] = {t2[i].first, t2[i].second};
    sort(queries.begin(), queries.end());
    vector<int> ans;
    int l = 0;
    for(auto p : queries){
        while(l < p.first){
            for(int y : next[l]) ministers.set(y, 1);
            l++;
        }
        int mini = ministers.sum(p.first, p.second + 1) - lcas.sum(p.first, p.second + 1);
        //cout << "P.first "<< p.first << " "<< p.second << " pos "<< pos[p.first] << " "<< mini << endl;
        //cout << "Sum "<< ministers.sum(p.first, p.second + 1) << " lca "<< lcas.sum(p.first, p.second + 1) << endl;
        if(mini >= k){
            ans.push_back(id[pos[p.first]]);
        }
    }
    sort(ans.begin(), ans.end()); cout << ans.size() << endl; for(int x : ans) {cout << x << " ";} cout << endl;
}

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

    //freopen("inpt.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    //int tt; cin >> tt;
    int tt = 1;
    for(int t = 1; t <= tt; t++){
        //cout << "Case #"<<t << ": ";
        solve();
    }
}

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