Submission #1308112

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308112		harryleee	Railway (BOI17_railway)	C++20	36 / 100	67 ms	25420 KiB

railway

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5;
int n, m, k, ttime, cur_chain = 1, th[maxn + 1];
int child[maxn + 1], par[maxn + 1], in[maxn + 1], out[maxn + 1], chain_id[maxn + 1], chain_head[maxn + 1], re[maxn + 1];
vector<pair<int, int>> adj[maxn + 1];

inline void DFS(int u, int p){
    par[u] = p;
    child[u] = 1;

    for (auto [v, id] : adj[u]) if (v != p){
        th[v] = id;
        DFS(v, u);
        child[u] += child[v];
    }
    return;
}       

inline void hld(int u, int p){
    if (chain_head[cur_chain] == 0){
        chain_head[cur_chain] = u;
    }
    in[u] = ++ttime;
    re[ttime] = u;
    chain_id[u] = cur_chain;
    int mx = -1;
    for (auto [v, id] : adj[u]) if (v != p){
        if (mx == -1 || child[v] > child[mx]) mx = v;
    }
    if (mx != -1) hld(mx, u);
    for (auto [v, id] : adj[u]) if (v != p && v != mx){
        ++cur_chain;
        hld(v, u);
    }
    out[u] = ttime;
    return;
}

struct SEGMENT_TREE{
    vector<int> st;
    inline void init(int n){
        st.resize(4 * n + 4, 0);
    }
    inline void update(int ind, int l, int r, int lb, int rb, int val){
        if (lb > rb) return;
        if (l >= lb && r <= rb){
            st[ind] += val;
            return;
        }
        int mid = (l + r) >> 1;
        if (mid >= lb) update(ind << 1, l, mid, lb, rb, val);
        if (mid < rb) update(ind << 1 | 1, mid + 1, r, lb, rb, val);
        return;
    }
    inline int get(int ind, int l, int r, int pos){
        if (l == r) return st[ind];
        int mid = (l + r) >> 1;
        if (mid >= pos) return st[ind] + get(ind << 1, l, mid, pos);
        else return st[ind] + get(ind << 1 | 1, mid + 1, r, pos);
    }
} seg;

inline int ancestor(int u, int v){
    while (chain_id[u] != chain_id[v]){
        if (chain_id[u] < chain_id[v]) swap(u, v);
        while(chain_id[u] > chain_id[v]){
            u = par[chain_head[chain_id[u]]];
        }
    }
    if (in[u] > in[v]) return v;
    return u;
}

inline void increase(int u, int v){
    while (chain_id[u] != chain_id[v]){
        if (chain_id[u] < chain_id[v]) swap(u, v);
        while(chain_id[u] > chain_id[v]){
            seg.update(1, 1, n, in[chain_head[chain_id[u]]], in[u], 1);
            u = par[chain_head[chain_id[u]]];
        }
    }
    if (in[u] != in[v]){
        if (in[u] < in[v]) swap(u, v);
        seg.update(1, 1, n, in[v], in[u], 1);
    }
    if (in[u] > in[v]) swap(u, v);
    seg.update(1, 1, n, in[u], in[u], -1); 
    return;
}

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

    cin >> n >> m >> k;
    seg.init(n);
    for (int i = 1, u , v; i < n; ++i){
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }

    DFS(1, -1);
    hld(1, -1);

    for (int i = 1; i <= m; ++i){
        int num; cin >> num;
        vector<int> v(num);
        for (int i = 0; i < num; ++i) cin >> v[i];
        sort(v.begin(), v.end(), [](int x, int y){
            return in[x] < in[y];
        });

        for (int i = 1; i < num; ++i) v.push_back(ancestor(v[i - 1], v[i]));

        sort(v.begin(), v.end(), [](int x, int y){
            return in[x] < in[y];
        });
        v.erase(unique(v.begin(), v.end()), v.end());


        stack<int> st;
        for (int i = 0; i < v.size(); ++i){
            while (!st.empty()){
                int cur = st.top();
                if (!(in[cur] <= in[v[i]] && out[v[i]] <= out[cur])) st.pop();
                else break;
            }
            if (!st.empty()){
                int cur = st.top();
                increase(cur, v[i]);
            }
            st.push(v[i]);
        }
    }

    vector<int> res;
    for (int i = 2; i <= n; ++i) if (seg.get(1, 1, n, i) >= k)
        res.push_back(th[re[i]]);
    sort(res.begin(), res.end());

    cout << res.size() << '\n';
    for (int x : res) cout << x << ' ';

    return 0;
}

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