Submission #390915

#TimeUsernameProblemLanguageResultExecution timeMemory
390915VictorRailway (BOI17_railway)C++17
23 / 100
1090 ms14264 KiB
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define per(i, a, b) for (int i = b - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;

const int INF = 1000000007;

int n, m, k, cnt[100001], layer[100001], curr;
vii graph[100001];

bool dfs(int u, int p) {
    bool ret = (layer[u] == curr);
    trav(edge, graph[u]) if (edge.first != p) {
        if (dfs(edge.first, u)) ++cnt[edge.second], ret = 1;
    }
    return ret;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    memset(cnt, 0, sizeof(cnt));
    memset(layer, -1, sizeof(layer));
    cin >> n >> m >> k;
    int a, b;
    rep(i, 0, n - 1) {
        cin >> a >> b;
        graph[--a].emplace_back(--b, i);
        graph[b].emplace_back(a, i);
    }
    
    rep(i, 0, m) {
        int s, u;
        curr = i;
        cin >> s;
        rep(j, 0, s) cin >> u, layer[u - 1] = i;
        dfs(u - 1, u - 1);
    }

    vi ans;
    rep(i, 0, n) {
        if (k <= cnt[i]) ans.pb(i + 1);
    }

    cout << sz(ans) << endl;
    trav(edge, ans) cout << edge << ' ';
    cout << endl;
    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...