Submission #170999

#	Time	Username	Problem	Language	Result	Execution time	Memory
170999		Rods	Railway (BOI17_railway)	C++14	100 / 100	450 ms	55628 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 mlg = 23;
const int sigma = 30;
int n, m, k, t, posorder = 0;

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

int par[ms][mlg+1], lvl[ms];

void dfs(int v, int p, int l = 0) { // chamar como dfs(root, root)
  lvl[v] = l;
  par[v][0] = p;
  order[v] = posorder++;
  for(int k = 1; k <= mlg; k++) {
    par[v][k] = par[par[v][k-1]][k-1];
  }
  for(int u : g[v]) {
    if(u != p) dfs(u, v, l + 1);
  }
}

int lca(int a, int b) {
  if(lvl[b] > lvl[a]) swap(a, b);
  for(int i = mlg; i >= 0; i--) {
    if(lvl[a] - (1 << i) >= lvl[b]) a = par[a][i];
  }
  if(a == b) return a;
  for(int i = mlg; i >= 0; i--) {
    if(par[a][i] != par[b][i]) a = par[a][i], b = par[b][i];
  }
  return par[a][0];
}

bool comp(int a, int b){
  return order[a]<order[b];
}

int get_ans(int a, int p){
  bool ans = 0;
  int total = 0;

  for(auto x: g[a]){

    if(x==p) continue;

    int d = id[{a, x}];
    int cc = get_ans(x, a);
    // cout<<d<<' '<<cc<<endl;
    h[d] = cc;
    total += cc;

  }

  total += pres[a];
  return total;
}

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

  int root = 1;
  dfs(root, root);

  for(int i=0; i<m; i++){
    cin>>qt;
    int up = -1;
    vi cc;
    while(qt--){
      
      cin>>a;
      cc.pb(a);
      pres[a]++;

    }
    sort(all(cc), comp);
    up = cc[0];
    for(int i=1; i<cc.size(); i++){
      int cur_lca = lca(cc[i-1], cc[i]);
      pres[cur_lca]--;
      up = lca(up, cur_lca);
    }
    pres[up]--;
  }
  get_ans(root, root);

  for(auto x: h){
    // cout<<x.x<<' '<<x.y<<endl;
    if(x.y>=k) res.insert(x.x);
  }

  cout<<res.size()<<endl;
  for(auto x: res){
    cout<<x+1<<' ';
  }
}

Compilation message (stderr)

railway.cpp: In function 'int get_ans(int, int)':
railway.cpp:61:8: warning: unused variable 'ans' [-Wunused-variable]
   bool ans = 0;
        ^~~
railway.cpp: In function 'int32_t main()':
railway.cpp:108:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<cc.size(); i++){
                  ~^~~~~~~~~~

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