Submission #1166241

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166241		bibocat	Railway (BOI17_railway)	C++20	7 / 100	51 ms	27320 KiB

railway

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int NMAX = 1e5 + 5;
const int LOG = 17;

int n, m, threshold;  // n: số nút, m: số truy vấn (phó bộ trưởng), threshold: số k (ít nhất k phó bộ trưởng)
vector<pair<int, int>> edges;      // danh sách cạnh: mỗi cạnh nối hai nút (u, v)
vector<int> adj[NMAX];             // danh sách kề lưu trữ chỉ số của cạnh
int st[NMAX], en[NMAX];            // thời gian vào và ra của mỗi nút trong DFS
int timer = 0;
int parentEdge[NMAX];              // parentEdge[v] lưu chỉ số cạnh nối v với cha của nó
int anc[NMAX][LOG];                // bảng tổ tiên dùng cho truy vấn LCA
int add[NMAX];                     // mảng hiệu dùng để lưu số lần "yêu cầu" của các cạnh
vector<int> result;                // danh sách kết quả (các cạnh được yêu cầu đủ số phi bộ trưởng)

// DFS tiền xử lý: tính thời gian vào/ra và xây dựng bảng tổ tiên
void dfsPreprocess(int u, int p) {
    st[u] = ++timer;
    anc[u][0] = p;  // tổ tiên cấp 0 là cha của u
    for (int i = 1; i < LOG; i++) {
        anc[u][i] = anc[anc[u][i-1]][i-1];
    }
    // duyệt các cạnh từ u
    for (int edgeIdx : adj[u]) {
        // Tìm nút đối diện của u trên cạnh edgeIdx
        int v = (edges[edgeIdx].first == u ? edges[edgeIdx].second : edges[edgeIdx].first);
        if (v == p) continue;
        parentEdge[v] = edgeIdx;  // lưu lại cạnh nối v với u
        dfsPreprocess(v, u);
    }
    en[u] = timer;
}

// Kiểm tra: u có là tổ tiên của v không?
bool isAncestor(int u, int v) {
    return st[u] <= st[v] && en[v] <= en[u];
}

// Tìm LCA của hai nút u và v
int lca(int u, int v) {
    if (isAncestor(u, v)) return u;
    for (int i = LOG - 1; i >= 0; i--) {
        if (!isAncestor(anc[u][i], v))
            u = anc[u][i];
    }
    return anc[u][0];
}

// DFS duyệt lại cây để cộng dồn các giá trị hiệu và xác định các cạnh đạt yêu cầu
int dfsAggregate(int u, int p) {
    int sum = 0;
    for (int edgeIdx : adj[u]) {
        int v = (edges[edgeIdx].first == u ? edges[edgeIdx].second : edges[edgeIdx].first);
        if (v == p) continue;
        int curVal = dfsAggregate(v, u) + add[edgeIdx];
        // Nếu số lần yêu cầu của cạnh >= threshold, thêm vào kết quả
        if (curVal >= threshold) {
            result.push_back(edgeIdx);
        }
        sum += curVal;
    }
    return sum;
}

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

    // Đọc dữ liệu: n - số nút, m - số truy vấn, threshold - yêu cầu tối thiểu
    cin >> n >> m >> threshold;
    
    // Đọc cây (n-1 cạnh). Mỗi cạnh được đánh số từ 0 đến n-2.
    for (int i = 1; i < n; i++){
        int u, v;
        cin >> u >> v;
        int edgeIdx = edges.size();
        edges.push_back({u, v});
        // Thêm cạnh vào danh sách kề của cả hai nút
        adj[u].push_back(edgeIdx);
        adj[v].push_back(edgeIdx);
    }
    
    // Tiền xử lý DFS để tính st, en và bảng LCA
    parentEdge[1] = -1; // nút gốc không có cạnh nối từ cha
    dfsPreprocess(1, 0);
    
    // Xử lý từng truy vấn của phó bộ trưởng
    // Mỗi truy vấn: đầu tiên là số s (số nút trong danh sách), sau đó là danh sách các nút.
    for (int i = 0; i < m; i++){
        int s;
        cin >> s;
        vector<int> nodes(s);
        for (int j = 0; j < s; j++){
            cin >> nodes[j];
        }
        // Sắp xếp các nút theo thời gian vào của DFS
        sort(nodes.begin(), nodes.end(), [](int a, int b){
            return st[a] < st[b];
        });
        
        // Xử lý các cặp liên tiếp theo thứ tự sắp xếp
        // Ý tưởng: nối dần các nút theo thứ tự, cập nhật hiệu dương ở đầu đoạn và hiệu âm tại điểm chung (LCA)
        int currentLCA = nodes[0];
        for (int j = 1; j < s; j++){
            int nextNode = nodes[j];
            // Tìm LCA của currentLCA và nextNode
            int common = lca(currentLCA, nextNode);
            // Cập nhật: tăng đếm từ nextNode lên (qua cạnh nối đến cha)
            add[parentEdge[nextNode]] += 1;
            // Giảm đếm tại cạnh của nút common (điều chỉnh trùng lặp)
            if (parentEdge[common] != -1) {
                add[parentEdge[common]] -= 1;
            }
            currentLCA = nextNode; // nối dần
        }
    }
    
    // Duyệt lại cây để tổng hợp giá trị trên các cạnh
    dfsAggregate(1, 0);
    
    // Sắp xếp kết quả theo thứ tự tăng dần (lưu ý: chuyển chỉ số cạnh về 1-index khi in)
    sort(result.begin(), result.end());
    cout << result.size() << "\n";
    for (int edgeIdx : result)
        cout << edgeIdx + 1 << " ";
    
    return 0;
}

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