Submission #472243

#TimeUsernameProblemLanguageResultExecution timeMemory
472243elgamalsalmanRailway (BOI17_railway)C++14
23 / 100
1087 ms17004 KiB
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second

typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<vii> vvii;

int n, m, k, markCount[100050];
vvii adj;
vii edges;
bitset<100050> visited, isDest;

bool dfs(int u) {
  if (visited[u]) return 0;
  visited[u] = 1;
  bool takeEdges = isDest[u];
  for (ii edge : adj[u]) {
    int v = edge.fi;
    int edgeInd = edge.se;
    if (!visited[v]) {
      if (dfs(v)) {
	takeEdges = 1;
	markCount[edgeInd]++;
      }
    }
  }
  
  return takeEdges;
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m >> k;
  adj.assign(n + 20, vii());
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    edges.push_back({a, b});
    adj[a].push_back({b, i});
    adj[b].push_back({a, i});
  }

  for (int j = 0; j < m; j++) {
    int s, start;
    cin >> s >> start;
    isDest.reset();
    for (int i = 0; i < s - 1; i++) {
      int tmp; cin >> tmp;
      isDest[tmp] = 1;
    } 
    visited.reset();
    dfs(start);
  }


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

  cout << (int)ans.size() << '\n';
  for (int i = 0; i < (int)ans.size(); i++) {
    if (i) cout << ' ';
    cout << ans[i] + 1;
  }
  cout << '\n';
}
#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...