Submission #1115682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115682		f0rizen	Railway (BOI17_railway)	C++17	36 / 100	92 ms	22212 KiB

railway

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int inf = 1e9 + 7;
const ll infll = 1e18;

template<typename T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i : a) {
        is >> i;
    }
    return is;
}

struct Edge {
    int to, ind;
};

struct BinaryJumps {
    static const int lg = 17;

    vector<int> d;
    vector<vector<int>> up;

    BinaryJumps() {}
    BinaryJumps(int n) {
        d.resize(n);
        up.resize(lg, vector<int>(n, -1));
    }

    void add_leaf(int v, int p) {
        d[v] = d[p] + 1;
        up[0][v] = p;
        for (int i = 1; i < lg; ++i) {
            if (up[i - 1][v] != -1) {
                up[i][v] = up[i - 1][up[i - 1][v]];
            }
        }
    }

    int la(int v, int k) {
        for (int i = lg - 1; i >= 0; --i) {
            if (k >= (1 << i)) {
                k -= (1 << i);
                v = up[i][v];
            }
        }
        return v;
    }

    int lca(int u, int v) {
        if (d[u] < d[v]) {
            swap(u, v);
        }
        u = la(u, d[u] - d[v]);
        for (int i = lg - 1; i >= 0; --i) {
            if (up[i][u] != up[i][v]) {
                u = up[i][u];
                v = up[i][v];
            }
        }
        if (u == v) {
            return u;
        }
        return up[0][u];
    }
};

vector<vector<Edge>> g;
BinaryJumps tr;
vector<int> tin, tout;
vector<int> edg;
vector<int> dp;
int timer = 0;

void dfs1(int v, int p = -1) {
    tin[v] = timer++;
    for (auto [u, i] : g[v]) {
        if (u != p) {
            tr.add_leaf(u, v);
            edg[u] = i;
            dfs1(u, v);
        }
    }
    tout[v] = timer;
}

bool is_anc(int p, int v) {
    return tin[p] <= tin[v] && tout[v] <= tout[p];
}

void dfs2(int v, int p = -1) {
    for (auto [u, i] : g[v]) {
        if (u != p) {
            dfs2(u, v);
            dp[v] += dp[u];
        }
    }
}

int32_t main() {
#ifdef LOCAL
    freopen("/tmp/input.txt", "r", stdin);
#else
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int n, m, k;
    cin >> n >> m >> k;
    g.resize(n);
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }
    tr = BinaryJumps(n);
    tin.resize(n);
    tout.resize(n);
    edg.resize(n);
    dfs1(0);
    dp.resize(n);
    for (int i = 0; i < m; ++i) {
        int s;
        cin >> s;
        vector<int> a(s);
        cin >> a;
        for (auto &v : a) {
            --v;
        }
        sort(a.begin(), a.end(), [&](int u, int v) {
            return tin[u] < tin[v];
        });
        a.push_back(a[0]);
        for (int i = 0; i < s; ++i) {
            int u = a[i];
            int v = a[i + 1];
            dp[u] += 1;
            dp[v] += 1;
            dp[tr.lca(u, v)] -= 2;
        }
    }
    dfs2(0);
    vector<int> ans;
    for (int i = 1; i < n; ++i) {
        if (dp[i] >= 2 * k) {
            ans.push_back(edg[i]);
        }
    }
    cout << ans.size() << "\n";
    for (auto i : ans) {
        cout << i + 1 << " ";
    }
    cout << "\n";
    return 0;
}

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