Submission #1163779

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163779		ChottuF	Railway (BOI17_railway)	C++20	100 / 100	79 ms	28360 KiB

railway

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 100005;
const int MAXH = 18; // since n <= 1e5, log2(n) < 18

int n, m, k;
vector<vector<int>> adj;
int depth[MAXN], parentArr[MAXN];
int up[MAXH][MAXN];
int tin[MAXN], tout[MAXN], timer = 0;
 
// DFS to compute tin/tout, depth and immediate parent.
void dfs(int u, int p, int d) {
    depth[u] = d;
    parentArr[u] = p;
    tin[u] = ++timer;
    up[0][u] = p;
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u, d+1);
    }
    tout[u] = timer;
}
 
// Standard binary lifting LCA.
int lca(int a, int b) {
    if(depth[a] < depth[b])
        swap(a, b);
    int d = depth[a] - depth[b];
    for (int i = 0; i < MAXH; i++){
        if(d & (1 << i))
            a = up[i][a];
    }
    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 parentArr[a];
}
 
// Global difference array.
// For each query we “update” the virtual tree edges by (conceptually)
// adding a query on the entire path from the virtual parent to the child.
// For a path update from u to v (with u an ancestor of v), the standard method is:
//    freq[u] += 1; freq[v] += 1; freq[u] -= 2   (since lca(u,v)==u)
// which is equivalent to: freq[u] -= 1; freq[v] += 1.
int freq[MAXN];
 
// After processing all queries we do a DFS (postorder) to accumulate the freq values:
// for every node v (other than the root), the final freq[v] will equal the number of queries that used
// the edge connecting v to its parent.
void dfsAccumulate(int u, int p) {
    for (int v : adj[u]) {
        if(v == p) continue;
        dfsAccumulate(v, u);
        freq[u] += freq[v];
    }
}
 
// Map each edge (stored as an ordered pair) to its track ID.
map<pair<int,int>, int> edgeId;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n >> m >> k;
    // Resize and initialize the tree.
    adj.resize(n+1);
    for (int i = 1; i <= n-1; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        int a = min(u, v), b = max(u, v);
        edgeId[{a, b}] = i;
    }
 
    // Precompute DFS order and binary lifting table.
    dfs(1, 0, 0);
    for (int i = 1; i < MAXH; i++){
        for (int u = 1; u <= n; u++){
            int par = up[i-1][u];
            up[i][u] = (par == 0 ? 0 : up[i-1][par]);
        }
    }
 
    // Process each deputy minister's query.
    // For each query we build the Steiner tree (i.e. the minimal subtree that connects the chosen nodes).
    // We do this by:
    //   1. Sorting the chosen nodes by tin.
    //   2. Adding the LCA for every consecutive pair.
    //   3. Removing duplicates and sorting again.
    //   4. Building the virtual tree using a stack.
    // For every virtual tree edge (u,v) with u as the parent (which equals lca(u,v)),
    // we update: freq[u] -= 1; freq[v] += 1;
    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(nodes.begin(), nodes.end(), [](int a, int b){
            return tin[a] < tin[b];
        });
 
        vector<int> virt = nodes;
        // Add LCAs of consecutive nodes.
        for (int i = 1; i < s; i++){
            int l = lca(nodes[i-1], nodes[i]);
            virt.push_back(l);
        }
        // Remove duplicates.
        sort(virt.begin(), virt.end(), [](int a, int b){ return tin[a] < tin[b]; });
        virt.erase(unique(virt.begin(), virt.end()), virt.end());
 
        // Build the virtual tree.
        vector<int> st;
        for (int u : virt) {
            while (!st.empty() && tout[st.back()] < tin[u])
                st.pop_back();
            if (!st.empty()){
                int par = st.back();
                // For a virtual edge from par to u (with par == lca(par, u)),
                // perform the update corresponding to a path update:
                // (freq[par] += 1, freq[u] += 1, freq[par] -= 2) <=> (freq[par] -= 1, freq[u] += 1).
                freq[par] -= 1;
                freq[u] += 1;
            }
            st.push_back(u);
        }
    }
 
    // Propagate the difference values: do a postorder DFS on the original tree.
    dfsAccumulate(1, 0);
 
    // For every edge (v, parent[v]) (v != 1) the final freq[v] is the number of queries that required that edge.
    vector<int> answer;
    for (int v = 2; v <= n; v++){
        if (freq[v] >= k) {
            int u = parentArr[v];
            int a = min(u, v), b = max(u, v);
            answer.push_back(edgeId[{a, b}]);
        }
    }
    sort(answer.begin(), answer.end());
    cout << answer.size() << "\n";
    for (int id : answer)
        cout << id << " ";
    cout << "\n";
    return 0;
}

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