Submission #472243

#	Time	Username	Problem	Language	Result	Execution time	Memory
472243		elgamalsalman	Railway (BOI17_railway)	C++14	23 / 100	1087 ms	17004 KiB

railway

#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';
}

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