Submission #170985

#TimeUsernameProblemLanguageResultExecution timeMemory
170985RodsRailway (BOI17_railway)C++14
8 / 100
1066 ms37504 KiB
#include <bits/stdc++.h>
// #define endl '\n'
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define x first
#define y second
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define ll long long
#define ld long double
#define ii pair<int, int>
#define iii pair<int, ii>
#define vi vector<int>
using namespace std;
const int ms = 2e5+100;
const int sigma = 30;
int n, m, k, t;

int pres[ms];
vi g[ms];
set<int> nec;
set<int> res;
map<ii, int> id;
map<int, int> h;

bool get_ans(int a, int p){
  bool ans = 0;
  for(auto x: g[a]){
    if(x==p) continue;
    bool aux = get_ans(x, a);
    ans= ans|| aux;
    if(aux){
      h[id[{a, x}]]++;
      if(h[id[{a, x}]]>=k){
        res.insert(id[{a, x}]);
      }
    }
  }
  return ans || nec.count(a); 
}

int32_t main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin>>n>>m>>k;
  int a, b, qt;
  for(int i=0; i<n-1; i++){
    cin>>a>>b;
    g[a].pb(b);
    g[b].pb(a);
    id[{a, b}] = id[{b, a}] = i;
  }
  for(int i=0; i<m; i++){
    cin>>qt;
    nec.clear();
    while(qt--){
      cin>>a;
      nec.insert(a);
    }
    get_ans(a, -1);
  }
  cout<<res.size()<<endl;
  for(auto x: res){
    cout<<x+1<<' ';
  }
}
#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...