Submission #1312986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312986		aaaaaaaa	Railway (BOI17_railway)	C++20	100 / 100	56 ms	22996 KiB

railway

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
const int mxN = 1e5 + 10;
const int mxB = 21;
vector<pair<int, int>> adj[mxN];
int st[mxN], eid[mxN], va[mxN], dp[mxN][mxB], depth[mxN], tin = 0;
void dfs(int u, int par){
    st[u] = ++tin, dp[u][0] = par, depth[u] = depth[par] + 1;
    dp[u][0] = par;
    for(int i = 1; i < mxB; ++i) dp[u][i] = dp[dp[u][i - 1]][i - 1];
    for(auto it : adj[u]){
        if(it.first ^ par){
            eid[it.first] = it.second;
            dfs(it.first, u);
        }
    }
}
void dfs2(int u, int par){
    for(auto it : adj[u]){
        if(it.first ^ par){
            dfs2(it.first, u);
            va[u] += va[it.first];
        }
    }
}
int kth(int u, int k){
        for(int i = 0; i < mxB; ++i){
            if(k & (1ll << i)) u = dp[u][i];
        }
        return u;
    }

    int lca(int u, int v){
        if(depth[u] < depth[v]) swap(u,v);
        u = kth(u, abs(depth[u] - depth[v]));
        if(u == v) return u;
        for(int i = mxB - 1; i >= 0; --i){
            if(dp[u][i] != dp[v][i]){
                u = dp[u][i];
                v = dp[v][i];
            }
        }
        return dp[u][0];
    }
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    for(int i = 1, u, v; i <= n - 1; ++i){
        cin >> u >> v;
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    } dfs(1, 0);
    auto update = [&](int u, int v) -> void {
        va[u] += 1, va[v] += 1;
        va[lca(u, v)] -= 2;
       // cout << lca(u, v) << " lca  " << u << " " << v << "\n";
    };
    while(m--){
        int sz; cin >> sz;
        vector<int> v(sz);
        for(int i = 0; i < sz; ++i) cin >> v[i];
        sort(all(v), [&](int x, int y){
            return st[x] < st[y];
        });
        v.push_back(v[0]);
        for(int i = 0; i < (int) v.size() - 1; ++i){
            update(v[i], v[i + 1]);
        }
    }
    dfs2(1, 0);
    vector<int> ans;
    for(int i = 2; i <= n; ++i){
        //cout << va[i] << " ";
        if(va[i] >= 2 * k) ans.push_back(eid[i]);
    } //cout << "\n";
    cout << (int) ans.size() << "\n";
    sort(all(ans));
    for(auto it : ans) cout << it << " ";
    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