Submission #1350654

#TimeUsernameProblemLanguageResultExecution timeMemory
1350654mikasaRailway (BOI17_railway)C++20
8 / 100
1094 ms13896 KiB
#include<bits/stdc++.h>
using namespace std;
#define debug(n,m) cout<<"["<<#n<<"]->"<<n<<m
#define int long long
#define all(x,off) x.begin()+off,x.end()
#define pb push_back 

const int N=1e6+10;
const int inf=9e17;
const int mod=1e9+7;
int n,m,k;

vector<int> g[N];
int in[N],out[N];
int x[N],y[N];

vector<int> ve[2001];

int tim=0;

void dfs(int u,int pa) {
  in[u]=++tim;
  for (int v : g[u]) {
    if (v==pa) continue;
    dfs(v,u);
  }
  out[u]=++tim;
}

int check(int idx) {
  int l=x[idx],r=y[idx];
  if (in[l]>in[r]&&out[l]<out[r]) swap(l,r);
  // debug(l,' ');
  // debug(r,'\n');
  int cnt=0;
  for (int i=1;i<=m;++i) {
    int cur=0;
    for (int el : ve[i]) {
      //if (!el) continue;
      if (in[el]>in[l]&&out[el]<out[l]&&in[el]>=in[r]&&out[el]<=out[r]){
        ++cur;
      } 
    }
    if (cur>0&&cur!=ve[i].size()&&ve[i].size()>1) {
      ++cnt; 
      // debug(cur,' ');
      // debug(i,'\n');
    }
  }
  return cnt;
}


void levi() {
  cin>>n>>m>>k;
  for (int i=1;i<n;++i ){
    cin>>x[i]>>y[i];
    g[x[i]].pb(y[i]);
    g[y[i]].pb(x[i]);
  }
  dfs(1,-1);
  for (int i=1;i<=m;++i) {
    int l;
    cin>>l;
    ve[i].resize(l);
    for (int j=1;j<=l;++j) {
      cin>>ve[i][j-1];
    }
  } 
  vector<int> v;
  for (int i=1;i<n;++i) {
    if (check(i)>=k) v.pb(i);
  }
  cout<<v.size()<<'\n';
  for (int id : v) {
    cout<<id<<" ";
  }
  cout<<'\n';
//sus
}

int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);int tt=1;//cin>>tt;
  while (tt--) levi();
}

/*


*/
#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...