Submission #245118

#	Time	Username	Problem	Language	Result	Execution time	Memory
245118		Tc14	Railway (BOI17_railway)	C++17	23 / 100	1100 ms	14456 KiB

railway

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ve vector
typedef long long ll;

int s;
ve<bool> C;
ve<int> E, U;
ve<ve<pair<int, int>>> G;

void edge(int u, int p) {

    int v;

    for (pair<int, int> e : G[u]) {
        v = e.first;
        if (v != p) {
            E[v] = e.second;
            edge(v, u);
        }
    }
}

int dfs(int u, int p) {

    int t, v;

    t = 0;
    for (pair<int, int> e : G[u]) {
        v = e.first;
        if (v != p) {
            t += dfs(v, u);
        }
    }

    if (C[u]) t++;
    if (t > 0 && t != s) U[u]++;

    return t;
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, k, a, b, ans;
    ve<int> S;

    cin >> n >> m >> k;
    G = ve<ve<pair<int, int>>>(n);
    E = ve<int>(n);
    U = ve<int>(n);

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

    edge(0, -1);

    for (int i = 0; i < m; i++) {
        cin >> s;
        C = ve<bool>(n);
        for (int j = 0; j < s; j++) {
            cin >> a;
            a--;
            C[a] = true;
        }
        dfs(0, -1);
    }

    ans = 0;
    for (int i = 1; i < n; i++) {
        if (U[i] >= k) {
            ans++;
            S.push_back(E[i]);
        }
    }

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

    cout << ans << endl;

    for (int i = 0; i < ans; i++) {
        cout << S[i] + 1 << " ";
    }
    cout << endl;

    return 0;
}

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