제출 #1343632

#제출 시각아이디문제언어결과실행 시간메모리
1343632kawhietRailway (BOI17_railway)C++20
0 / 100
35 ms15024 KiB
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 47
#endif

constexpr int N = 1e5;

vector<int> g[N];
int lvl[N], par[N], t[N];

void dfs_lvl(int u) {
    for (auto v : g[u]) {
        if (v != par[u]) {
            par[v] = u;
            lvl[v] = lvl[u] + 1;
            dfs_lvl(v);
        }
    }
}

void update(int u, int v) {
    if (lvl[u] > lvl[v]) swap(u, v);
    t[v]++;
    if (par[u] != -1) {
        t[par[u]]--;
    }
}

void dfs(int u) {
    for (auto v : g[u]) {
        if (v != par[u]) {
            dfs(v);
            t[u] += t[v];
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> u(n - 1), v(n - 1);
    for (int i = 0; i < n - 1; i++) {
        cin >> u[i] >> v[i];
        u[i]--; v[i]--;
        g[u[i]].push_back(v[i]);
        g[v[i]].push_back(u[i]);
    }
    par[0] = -1;
    dfs_lvl(0);
    for (int i = 0; i < m; i++) {
        int s;
        cin >> s;
        vector<int> a(s);
        for (int j = 0; j < s; j++) {
            cin >> a[j];
            a[j]--;
        }
        ranges::sort(a, [&](int x, int y) {
            return lvl[x] < lvl[y];
        });
        for (int pos = 1; pos < s; pos++) {
            update(a[pos - 1], a[pos]);
        }
    }
    dfs(0);
    vector<int> ans;
    for (int i = 0; i < n - 1; i++) {
        if (t[u[i]] >= k && t[v[i]] >= k) {
            ans.push_back(i + 1);
        }
    }
    cout << ans.size() << '\n';
    for (auto i : ans) {
        cout << i << ' ';
    }
    cout << '\n';
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...