Submission #1163777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163777		ChottuF	Railway (BOI17_railway)	C++20	0 / 100	117 ms	45316 KiB

railway

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5+5;
const int MAXH = 22;

vector<vector<int>> adj;
int up[MAXH][MAXN], depth[MAXN];
int tin[MAXN], tout[MAXN], timer = 0;

// DFS to compute depth, parent pointers, and tin/tout times.
void dfs(int x, int p, int d) {
    depth[x] = d;
    up[0][x] = p;
    tin[x] = ++timer;
    for(auto u : adj[x]) {
        if(u == p) continue;
        dfs(u, x, d+1);
    }
    tout[x] = timer;
}

int jmp(int x, int k) {
    for (int i = 0; i < MAXH; i++) {
        if(k & (1 << i))
            x = up[i][x];
    }
    return x;
}

int lca(int a, int b) {
    if(depth[a] < depth[b]) swap(a, b);
    a = jmp(a, depth[a]-depth[b]);
    if(a == b) return a;
    for (int i = MAXH-1; i >= 0; i--) {
        if(up[i][a] != up[i][b]) {
            a = up[i][a];
            b = up[i][b];
        }
    }
    return up[0][a];
}

// We'll use diff[node] to hold a mapping (query id -> count)
// representing the “difference” contributions from each query.
map<int,int> diff[MAXN];
// After merging, ans[x] will be the number of queries that contributed to the edge (x, parent[x]).
int ans[MAXN];

// DFS to merge difference maps using small-to-large merging.
void dfs2(int x, int p) {
    for(auto u : adj[x]) {
        if(u == p) continue;
        dfs2(u, x);
        if(diff[x].size() < diff[u].size()) swap(diff[x], diff[u]);
        for(auto &entry : diff[u]) {
            diff[x][entry.first] += entry.second;
            if(diff[x][entry.first] == 0)
                diff[x].erase(entry.first);
        }
    }
    ans[x] = diff[x].size();
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;
    adj.resize(n+1);
    // Map a track (stored as an ordered pair) to its ID.
    map<pair<int,int>, int> mpp;
    for (int i = 0; i < n-1; i++){
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        if(a > b) swap(a, b);
        mpp[{a, b}] = i+1;
    }
    
    // Precompute DFS order and LCA binary lifting arrays.
    dfs(1, 0, 1);
    for(int j = 1; j < MAXH; j++){
        for(int i = 1; i <= n; i++){
            up[j][i] = up[j-1][up[j-1][i]];
        }
    }

    // Process each deputy minister's query.
    for (int q = 0; q < m; q++){
        int s;
        cin >> s;
        vector<int> nodes(s);
        for (int i = 0; i < s; i++){
            cin >> nodes[i];
        }
        // Sort chosen nodes by their tin value.
        sort(nodes.begin(), nodes.end(), [&](int a, int b){
            return tin[a] < tin[b];
        });
        
        // Build the set of nodes for the Steiner tree:
        // start with the chosen nodes and add LCAs for consecutive ones.
        vector<int> steiner = nodes;
        for (int i = 1; i < s; i++){
            steiner.push_back(lca(nodes[i-1], nodes[i]));
        }
        sort(steiner.begin(), steiner.end(), [&](int a, int b){
            return tin[a] < tin[b];
        });
        steiner.erase(unique(steiner.begin(), steiner.end()), steiner.end());

        // Build the virtual tree using a stack.
        vector<int> st;
        // We will collect virtual tree edges as (parent, child).
        vector<pair<int,int>> vtEdges;
        for (int x : steiner) {
            while (!st.empty() && tout[st.back()] < tin[x]) {
                st.pop_back();
            }
            if (!st.empty()) {
                vtEdges.push_back({st.back(), x});
            }
            st.push_back(x);
        }
        // For every edge in the virtual tree, add a +1 contribution for query q at the child.
        for(auto &edge : vtEdges){
            int parent = edge.first, child = edge.second;
            diff[child][q] += 1;
        }
    }

    // Merge difference maps over the entire tree.
    dfs2(1, 0);

    // For every edge (represented by node i with parent up[0][i]), if the aggregated
    // contribution (number of queries that requested that edge) is at least k, include that track.
    vector<int> answerEdges;
    for (int i = 2; i <= n; i++){
        if(ans[i] >= k){
            int a = i, b = up[0][i];
            if(a > b) swap(a, b);
            answerEdges.push_back(mpp[{a, b}]);
        }
    }
    sort(answerEdges.begin(), answerEdges.end());
    cout << answerEdges.size() << "\n";
    for (auto x : answerEdges)
        cout << x << " ";
    cout << "\n";
    return 0;
}

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