Submission #878292

#	Time	Username	Problem	Language	Result	Execution time	Memory
878292		ArashJafariyan	Railway (BOI17_railway)	C++17	100 / 100	230 ms	36976 KiB

railway

#include <bits/stdc++.h>
using namespace std;

#define ll long long 
#define pb push_back
#define pii array<int, 2>

const int LG = 16 + 2, N = 1e5 + 4;

int n, m, k, anc[N][LG], h[N], bc[N], e[N], cnt[N];
vector<int> addSen[N], remSen[N];
vector<pii> g[N];
set<int> sack;

void findAnc(int v = 0, int p = 0) {
    if (v != 0) {
        for (int i = 1; i < LG; ++i) {
            int u = anc[v][i - 1];
            if (u != -1) {
                anc[v][i] = anc[u][i - 1];
            }
        }
    }

    for (auto [u, _] : g[v]) {
        if (u != p) {
            h[u] =  h[v] + 1;
            anc[u][0] = v;
            findAnc(u, v);
        }
    }
}

int lca(int v, int u) {
    if (v == u) {
        return v;
    }

    if (h[v] < h[u])
        swap(v, u);
    
    for (int i = 0; i < LG; ++i) {
        if ((1 << i) & (h[v] - h[u])) {
            v = anc[v][i];
        }
    }

    if (v == u) {
        return v;
    }

    for (int i = LG - 1; i >= 0; --i) {
        int vt = anc[v][i];
        int ut = anc[u][i];
        if (vt != ut && vt != -1 && ut != -1) {
            v = vt;
            u = ut;
        }
    }

    return anc[v][0];
}

int preDfs(int v = 0, int p = 0) {
    int ret = 1, cur = 0;
    for (auto [u, edge] : g[v]) {
        if (u != p) {
            e[u] = edge;
            int res = preDfs(u, v);
            ret += res;
            if (res > cur) {
                cur = res;
                bc[v] = u;
            }
        }
    }
    return ret;
}

void rem(int v, int p) {
    for (int sen : addSen[v]) {
        auto it = sack.find(sen);
        if (it != sack.end()) {
            sack.erase(it);
        }
    }

    for (auto [u, _] : g[v]) {
        if (u != p) {
            rem(u, v);
        }
    }
}

void add(int v, int p) {
    for (auto [u, _] : g[v]) {
        if (u != p) {
            add(u, v);
        }
    }

    for (int sen : addSen[v]) {
        sack.insert(sen);
    }
    for (int sen : remSen[v]) {
        auto it = sack.find(sen);
        if (it != sack.end()) {
            sack.erase(it);
        }
    }
}

void dfs(int v = 0, int p = 0) {
    for (auto [u, _] : g[v]) {
        if (u != p && u != bc[v]) {
            dfs(u, v);
            rem(u, v);
        }
    }

    if (bc[v] != -1) {
        dfs(bc[v], v);
    }
    for (auto [u, _] : g[v]) {
        if (u != p && u != bc[v]) {
            add(u, v);
        }
    }
    
    for (int sen : addSen[v]) {
        sack.insert(sen);
    }
    for (int sen : remSen[v]) {
        auto it = sack.find(sen);
        if (it != sack.end()) {
            sack.erase(it);
        }
    }

    if (v != 0) {
        cnt[e[v]] += sack.size();
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> k;
    for (int i = 0; i < n - 1; ++i) {
        int v, u;
        cin >> v >> u;
        --v, --u;
        g[v].pb({u, i});
        g[u].pb({v, i});
    }

    memset(anc, -1, sizeof anc);
    findAnc();

    for (int i = 0; i < m; ++i) {
        int sz;
        cin >> sz;
        int l = -1;
        while (sz--) {
            int v;
            cin >> v;
            --v;
            if (l == -1) {
                l = v;
            }
            else {
                l = lca(l, v);
            }
            addSen[v].pb(i);
        }
        remSen[l].pb(i);
    }

    memset(bc, -1, sizeof bc);
    preDfs();
    dfs();

    vector<int> out;
    for (int i = 0; i < n - 1; ++i) {
        if (cnt[i] >= k) {
            out.pb(i + 1);
        }
    }  

    cout << out.size() << '\n';
    for (int edge : out) {
        cout << edge << ' ';
    }

    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