Submission #651313

#	Time	Username	Problem	Language	Result	Execution time	Memory
651313		dooompy	Railway (BOI17_railway)	C++17	100 / 100	138 ms	28436 KiB

railway

#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

vector<int> adj[100005];
vector<int> person[50005];

int st[100005];
int timer = 1;
int h[100005];
int jmp[100005][20];

void dfs(int node, int par = -1) {
    st[node] = timer++;

    for (int j = 1; j < 20; j++) {
        jmp[node][j] = jmp[jmp[node][j-1]][j-1];
    }

    for (auto nxt : adj[node]) {
        if (nxt == par) continue;
        h[nxt] = h[node] + 1;
        jmp[nxt][0] = node;
        dfs(nxt, node);
    }
}

int lca(int a, int b) {
    if (h[a] > h[b]) swap(a, b);

    for (int j = 19; j >= 0; j--) {
        if (h[jmp[b][j]] >= h[a]) b = jmp[b][j];
    }

    if (a == b) return a;

    for (int j = 19; j >= 0; j--) {
        if (jmp[a][j] != jmp[b][j]) {
            a = jmp[a][j]; b = jmp[b][j];
        }
    }

    return jmp[a][0];
}


int node[100005];
int val[100005];

int dfs2(int cur, int par) {

    val[cur] = node[cur];
    for (auto nxt : adj[cur]) {
        if (nxt == par) continue;

        val[cur] += dfs2(nxt, cur);
    }

    return val[cur];
}

vector<pair<int, int>> edges;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int n, m, k; cin >> n >> m >> k;
    for (int i = 0; i < n - 1; i++) {
        int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); edges.emplace_back(a, b);
    }

    h[1] = 1;
    jmp[1][0] = 1;
    dfs(1);

    for (int i = 0; i < m; i++) {
        int s ;cin >> s;
        vector<int> temp;

        for (int j = 0; j < s; j++) {
            int t; cin >> t; temp.push_back(t);
        }

        sort(temp.begin(), temp.end(), [](int a, int b) {
            return st[a] < st[b];
        });

        for (int j = 0; j < s; j++) {
            int a = temp[j], b = temp[(j + 1) % s];

            int l = lca(a, b);

            node[a]++; node[b]++; node[l] -= 2;
        }
    }

    vector<int> ans;

    dfs2(1, -1);

    int i = 1;
    for (auto edge :edges) {
        int a = (h[edge.first] > h[edge.second] ? edge.first : edge.second);

        if (val[a] >= 2 * k) ans.push_back(i);
        i++;
    }

    cout << ans.size() << endl;
    for (auto a : ans) cout << a << " ";
}

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