Submission #785673

#	Time	Username	Problem	Language	Result	Execution time	Memory
785673		SlavicG	Railway (BOI17_railway)	C++17	100 / 100	210 ms	38344 KiB

railway

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

const int N = 1e5 + 5, K = 20;
vector<int> adj[N];
int jump[N][K], depth[N], tin[N], tt = 0, cnt[N];
void get_parents(int u, int par) {
    jump[u][0] = par;
    tin[u] = tt++;
    for(int v: adj[u]) {
        if(v == par) continue;
        depth[v] = depth[u] + 1;
        get_parents(v, u);
    }
}
int lca(int a, int b) {
    if(depth[a] < depth[b]) swap(a, b);
    for(int i = K - 1; i >= 0; --i) {
        if(depth[jump[a][i]] >= depth[b]) a = jump[a][i];
    }
    if(a == b) return a;
    for(int i = K - 1; i >= 0; --i) {
        if(jump[a][i] != jump[b][i]) {
            a = jump[a][i];
            b = jump[b][i];
        }
    }
    return jump[a][0];
}

void dfs(int u, int par) {
    for(int v: adj[u]) {
        if(v == par) continue;
        dfs(v, u);
        cnt[u] += cnt[v];
    }
}

void solve() {
    int n, m, k; cin >> n >> m >> k;
    map<pair<int, int>, int> mp;
    for(int i = 0; i < n - 1; ++i) {
        int u, v; cin >> u >> v; --u, --v;
        adj[u].pb(v);
        adj[v].pb(u);
        mp[{u, v}] = mp[{v, u}] = i;
    }
    get_parents(0, 0);
    for(int j = 1; j < K; ++j) {
        for(int i = 0; i < n; ++i) {
            jump[i][j] = jump[jump[i][j - 1]][j - 1];
        }
    }

    while(m--) {
        int len; cin >> len;
        vector<int> a(len);
        for(int i = 0; i < len; ++i) {
            cin >> a[i]; --a[i];
        }
        sort(all(a), [&](int i, int j){return tin[i] < tin[j];});
        vector<int> nodes = a;
        for(int i = 0; i + 1 < len; ++i) {
            nodes.pb(lca(a[i], a[i + 1]));
        }
        sort(all(nodes), [&](int i, int j){return tin[i] < tin[j];});
        nodes.erase(unique(all(nodes)), nodes.end());
        stack<int> st;
        st.push(nodes[0]);
        for(int i = 1; i < sz(nodes); ++i) {
            while(lca(st.top(), nodes[i]) != st.top()) st.pop();
            ++cnt[nodes[i]];
            --cnt[st.top()];
            st.push(nodes[i]);
        }
    }

    dfs(0, -1);
    vector<int> v;
    for(int i = 0; i < n; ++i) {
        if(cnt[i] >= k) {
            v.pb(mp[{i, jump[i][0]}]);
        }
    }
    sort(all(v));
    cout << sz(v) << "\n";
    for(auto x: v) cout << x + 1 << " ";

}   
 
int32_t main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) {
        solve();
    }
}

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