Submission #1144777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144777		Ariadna	Railway (BOI17_railway)	C++20	52 / 100	214 ms	31064 KiB

railway

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;

int log_n = 20;
vector<int> depth, idx;
vector<pair<int, int>> edges;
vector<vector<pair<int, int>>> adj;
vector<vector<int>> parent;

struct Segtree {
    int n;
    vector<int> st, lz;

    Segtree(int n) : n(n), st(vector<int>(4*n, 0)), lz(vector<int>(4*n, 0)) {};


    void change(int p, int l, int r, int i, int v) {
        if (l == r) st[p] += v;
        else {
            int m = (l+r)/2;
            if (i <= m) change(2*p, l, m, i, v);
            else change(2*p+1, m+1, r, i, v);
            st[p] = st[2*p]+st[2*p+1];
        }
    }

    int sum(int p, int l, int r, int i, int j) {
        if (i > j) return 0;
        if (i == l && j == r) return st[p];
        int m = (l+r)/2;
        return sum(2*p, l, m, i, min(m, j))+sum(2*p+1, m+1, r, max(i, m+1), j);
    }

    void change(int i, int v) { change(1, 0, n-1, i, v); }
    int sum(int i, int j) { return sum(1, 0, n-1, i, j); }
};

int jump(int u, int k) {
    for (int i = 0; i < log_n; ++i) {
        if (k&(1<<i)) u = parent[u][i];
    }
    return u;
}

int LCA(int a, int b) {
    if (depth[a] > depth[b]) swap(a, b);
    b = jump(b, depth[b]-depth[a]);
    if (a == b) return a;

    for (int i = log_n-1; i >= 0; --i) {
        if (parent[a][i] != parent[b][i]) {
            a = parent[a][i];
            b = parent[b][i];
        }
    }

    return parent[b][0];
}

int cnt = 0;
void dfs(int u, int p) {
    edges[u].fi = cnt;
    parent[u][0] = p;
    depth[u] = depth[p]+1;
    for (int i = 1; i < log_n; ++i) {
        parent[u][i] = parent[parent[u][i-1]][i-1];
    }

    for (pair<int, int> v: adj[u]) {
        if (v.fi == p) continue;
        ++cnt;
        dfs(v.fi, u);
        idx[v.fi] = v.se;
    }
    edges[u].se = cnt;
}

void solve(int n, int m, int k) {
    Segtree St(n);
    while (m--) {
        int s; cin >> s;
        vector<pair<int, int>> nodes(s);
        for (int i = 0; i < s; ++i) {
            cin >> nodes[i].se;
            nodes[i].se--;
            nodes[i].fi = edges[nodes[i].se].fi;
        }

        sort(nodes.begin(), nodes.end());

        for (int i = 1; i <= s; ++i) {
            int lca = LCA(nodes[i%s].se, nodes[i-1].se); 
            St.change(edges[nodes[i%s].se].fi, 1);
            St.change(edges[nodes[i-1].se].fi, 1);
            St.change(edges[lca].fi, -2);
        }
    }
    vector<int> ans;
    for (int i = 0; i < n-1; ++i) {
        if (St.sum(edges[i].fi, edges[i].se) >= 2*k) ans.pb(idx[i]);
    }

    sort(ans.begin(), ans.end());
    cout << (int)ans.size() << endl;
    for (int i: ans) cout << i << " ";
    cout << endl;
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    depth = idx = vector<int>(n, -1);
    adj = vector<vector<pair<int, int>>>(n);
    parent = vector<vector<int>>(n, vector<int>(log_n));
    edges = vector<pair<int, int>>(n);

    for (int i = 0; i < n-1; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        adj[a].pb({b, i+1});
        adj[b].pb({a, i+1});
    }
    dfs(0, 0);

    solve(n, m, k);

    return 0;
}

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