제출 #1194670

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194670		julia_08	Railway (BOI17_railway)	C++20	23 / 100	1096 ms	15104 KiB

railway

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

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