Submission #1322476

#TimeUsernameProblemLanguageResultExecution timeMemory
1322476s0me0neRailway (BOI17_railway)C++20
100 / 100
80 ms25756 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static const int MAXN = 100'005;
int n, m, k;
// trying out maxn just to see the speed increase
vector<pair<int,int>> adj[MAXN];
int p[20][MAXN], depth[MAXN], tin[MAXN], tout[MAXN], timer, pedge[MAXN];
ll diff[MAXN], ecnt[MAXN];

void dfs(int u, int rt, int pe) {
    p[0][u] = rt;
    pedge[u] = pe;
    tin[u] = ++timer;
    for (auto [v, id] : adj[u]) {
        if (v == rt) continue;
        depth[v] = depth[u] + 1;
        dfs(v, u, id);
    }
    tout[u] = timer;
}

int lca(int a, int b) {
    if (depth[a] < depth[b]) swap(a, b);
    for (int i = 19; i >= 0; i--)
        if (p[i][a] && depth[p[i][a]] >= depth[b])
            a = p[i][a];
    if (a == b) return a;
    for (int i = 19; i >= 0; i--)
        if (p[i][a] && p[i][a] != p[i][b]) {
            a = p[i][a];
            b = p[i][b];
        }
    return p[0][a];
}

void dfs2(int u, int rt) {
    for (auto [v, id] : adj[u]) {
        if (v == rt) continue;
        dfs2(v, u);
        diff[u] += diff[v];
        ecnt[id] = diff[v];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> k;
    for (int i = 1; i <= n - 1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
    }
    dfs(1, 0, 0);
    for (int i = 1; i < 20; i++)
        for (int v = 1; v <= n; v++)
            p[i][v] = p[i - 1][p[i - 1][v]];
    while (m--) {
        int s;
        cin >> s;
        vector<int> nodes(s);
        for (int i = 0; i < s; i++) cin >> nodes[i];
        sort(nodes.begin(), nodes.end(), [&](int a, int b) { return tin[a] < tin[b]; });
        vector<int> vt = nodes;
        for (int i = 0; i + 1 < nodes.size(); i++)
            vt.push_back(lca(nodes[i], nodes[i + 1]));
        sort(vt.begin(), vt.end(), [&](int a, int b) { return tin[a] < tin[b]; });
        vt.erase(unique(vt.begin(), vt.end()), vt.end());
        stack<int> st;
        st.push(vt[0]);
        for (int i = 1; i < vt.size(); i++) {
            int u = vt[i];
            while (!st.empty() &&
                   !(tin[st.top()] <= tin[u] && tin[u] <= tout[st.top()]))
                st.pop();
            int v = st.top(), w = lca(u, v);
            diff[u]++;
            diff[v]++;
            diff[w] -= 2;
            st.push(u);
        }
    }
    dfs2(1, 0);
    vector<int> ans;
    for (int i = 1; i <= n - 1; i++)
        if (ecnt[i] >= k)
            ans.push_back(i);
    cout << ans.size() << '\n';
    for (int x : ans) cout << x << ' ';
    cout << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...