Submission #246586

#	Time	Username	Problem	Language	Result	Execution time	Memory
246586		santaclaus03	Railway (BOI17_railway)	C++14	100 / 100	378 ms	43760 KiB

railway

#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

int n, m, k; 
vvi tree, anc;
vi discovery, finish, v, ans;
map<ii, int> edge_idx;
int t = 0;

void pre(int u, int p) {
    discovery[u] = t++;
    anc[u][0] = p;
    for (int i = 1; i < 20; ++i) anc[u][i] = anc[anc[u][i - 1]][i - 1];
    for (int v : tree[u]) if (v != p) pre(v, u);
    finish[u] = t++;
}

bool is_anc(int a, int b) {
    return discovery[a] <= discovery[b] && finish[b] <= finish[a];
}

int lca(int a, int b) {
    if (is_anc(a, b)) return a;
    if (is_anc(b, a)) return b;
    for (int step = 19; step >= 0; --step) {
        if (!is_anc(anc[a][step], b)) a = anc[a][step];
    }
    return anc[a][0];
}

int dfs(int u, int p) {
    int res = v[u];
    for (int v : tree[u]) if (v != p) {
        int c = dfs(v, u);
        res += c;
        if (c >= k) ans.push_back(edge_idx[{ u, v }]);
    }
    return res;
}

int main() {
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    cin >> n >> m >> k;
    tree.resize(n); anc.resize(n, vi(20));
    discovery.resize(n); finish.resize(n); v.resize(n);
    for (int i = 1; i < n; ++i) {
        int a, b; cin >> a >> b; a--; b--;
        tree[a].push_back(b); tree[b].push_back(a);
        edge_idx[{a, b}] = edge_idx[{b, a}] = i;
    }
    pre(0, 0);
    for (int i = 0; i < m; ++i) {
        int s; cin >> s;
        vi nodes(s); 
        for (int &x : nodes) {
            cin >> x; x--;
            v[x]++;
        }
        sort(nodes.begin(), nodes.end(), [&](int a, int b) { return discovery[a] < discovery[b]; });
        for (int j = 0; j < s; ++j) {
            int a = nodes[j], b = nodes[(j + 1) % s];
            int l = lca(a, b);
            v[l]--;
        }
    }
    dfs(0, -1);
    sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for (int e : ans) cout << e << " ";
}

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