Submission #1194670

#TimeUsernameProblemLanguageResultExecution timeMemory
1194670julia_08Railway (BOI17_railway)C++20
23 / 100
1096 ms15104 KiB
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 10;

int sub[MAXN], cnt[MAXN];

int marc[MAXN];

vector<pair<int, int>> adj[MAXN];

void dfs(int v, int p, int s){

  sub[v] = marc[v];

  for(auto [u, i] : adj[v]){

    if(u != p){
      dfs(u, v, s);
      sub[v] += sub[u];
      if(sub[u] > 0 && s - sub[u] > 0) cnt[i] ++;
    }

  }

}

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

  int n, m, k; cin >> n >> m >> k;

  for(int i=1; i<n; i++){

    int a, b; cin >> a >> b;

    adj[a].push_back({b, i});
    adj[b].push_back({a, i});

  }

  while(m--){

    int s; cin >> s;

    vector<int> vtx(s);

    for(int i=0; i<s; i++){
      cin >> vtx[i];
      marc[vtx[i]] ++;
    }

    dfs(1, 1, s);

    for(int i=0; i<s; i++) marc[vtx[i]] --;

  }

  vector<int> ans;

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

  cout << (int) ans.size() << "\n";

  for(auto x : ans) cout << x << " ";

  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...