Submission #1026349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026349		gyg	Railway (BOI17_railway)	C++17	100 / 100	239 ms	66992 KiB

railway

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAX_N = 1e5 + 5, INF = 1e9;

int n, m, k;
map<pii, int> edge_ind; // Both ways
array<vector<int>, MAX_N> adj;

array<vector<int>, MAX_N> children;
int n_inds;
array<int, MAX_N> ind, f_ind, rev_ind;
array<array<int, 20>, MAX_N> anc;
void dfs1(int u = 1) {
    n_inds++, ind[u] = n_inds, rev_ind[n_inds] = u;
    for (int v : adj[u])
        if (!ind[v]) children[u].push_back(v), anc[v][0] = u, dfs1(v);
    f_ind[u] = n_inds;   
}
bool is_anc(int u, int v) { return ind[u] <= ind[v] && ind[v] <= f_ind[u]; }
int lca(int u, int v) {
    if (is_anc(u, v)) return u;
    if (is_anc(v, u)) return v;
    for (int i = 19; i >= 0; i--)
        if (anc[u][i] != 0 && !is_anc(anc[u][i], v)) 
            u = anc[u][i];
    u = anc[u][0];
    return u;
}
void precomp() {
    dfs1();
    for (int i = 1; i < 20; i++)
        for (int u = 1; u <= n; u++) 
            anc[u][i] = anc[anc[u][i - 1]][i - 1];
}

array<vector<int>, MAX_N> add, del;
array<unordered_set<int>, MAX_N> groups;
array<int, MAX_N> n_groups;
void merge(unordered_set<int>& x, unordered_set<int>& y) { // y ---> x
    if (x.size() < y.size()) x.swap(y);
    for (int z : y) x.insert(z);
}
void dfs2(int u = 1) {
    for (int v : children[u]) 
        dfs2(v), merge(groups[u], groups[v]);
    
    groups[u].insert(add[u].begin(), add[u].end());
    for (int x : del[u]) 
        if (groups[u].count(x)) groups[u].erase(x);

    // cout << u << ": ";
    // for (int x : groups[u]) cout << x << " ";
    // cout << endl;
    
    n_groups[u] = groups[u].size();
}

int main() {
    // freopen("rail.in", "r", stdin);
    cin >> n >> m >> k;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        edge_ind[{u, v}] = edge_ind[{v, u}] = i;
        adj[u].push_back(v), adj[v].push_back(u);        
    }

    precomp();

    for (int i = 1; i <= m; i++) {
        int siz; cin >> siz;
        vector<int> nodes;
        for (int j = 1; j <= siz; j++) {
            int u; cin >> u;
            nodes.push_back(u);
            add[u].push_back(i);
        }

        int min_ind = INF, max_ind = -1;
        for (int u : nodes) min_ind = min(min_ind, ind[u]), max_ind = max(max_ind, ind[u]);
        int lca_node = lca(rev_ind[min_ind], rev_ind[max_ind]);
        del[lca_node].push_back(i);
        // cout << i << ": " << lca_node << endl;
    }

    dfs2();

    set<int> ans;
    for (int u = 2; u <= n; u++) {
        if (n_groups[u] < k) continue;
        int par = anc[u][0];
        ans.insert(edge_ind[{u, par}]);
    }

    cout << ans.size() << '\n';
    for (int u : ans) cout << u << " ";
    cout << '\n';
}

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