Submission #170985

#	Time	Username	Problem	Language	Result	Execution time	Memory
170985		Rods	Railway (BOI17_railway)	C++14	8 / 100	1066 ms	37504 KiB

railway

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

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