Submission #535656

#	Time	Username	Problem	Language	Result	Execution time	Memory
535656		nemethm	Railway (BOI17_railway)	C++17	36 / 100	346 ms	74320 KiB

railway

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <list>

using namespace std;
using ll = long long int;

vector<int> g[100100];
int dp[100100][30];
set<int> in[100100], out[100100];
int level[100100];
map<pair<int,int>,int> id;
vector<int> ans;
int k;
void dfs(int node, int prev = 0, int l = 1){
  level[node] = l;
  dp[node][0] = prev;
  for(auto i : g[node]){
    if(i != prev){
      dfs(i, node, l + 1);
    }
  }
}

int jump(int a, int x){
    for(int i = 0; i < 20; ++i){
        if((x >> i) & 1){
            a = dp[a][i];
        }
    }
    return a;
}

int lca(int a, int b){
    if(level[a] < level[b]) swap(a,b);
    a = jump(a, level[a] - level[b]);
    if(a == b) return a;
    for(int i = 20; i >= 0; --i){
        if(dp[a][i] != dp[b][i]){
            a = dp[a][i], b = dp[b][i];
        }
    }
    return dp[a][0];
}

set<int> solve(int node, int prev = -1){
  set<int> open = in[node];
  for(auto i : g[node]){
    if(i != prev){
      set<int> a = solve(i, node);
      if(a.size() >= k){
        ans.push_back(id[{node, i}]);
      }
      if(a.size() > open.size()) swap(a, open);
      for(auto& j : a){
        open.emplace(j);
      }
    }
  }
  for(auto& i : out[node]){
    open.erase(i);
  }
  return open;
}

int main()
{
  int n, m;
  cin >> n >> m >> k;
  for(int i = 0; i < n - 1; ++i){
    ll a, b;
    cin >> a >> b;
    g[a].emplace_back(b), g[b].emplace_back(a);
    id[{a,b}] = id[{b,a}] = i + 1;
  }
  dfs(1);
  for(int i = 1; i < 20; ++i){
    for(int node = 1; node <= n; ++node){
      dp[node][i] = dp[dp[node][i - 1]][i - 1];
    }
  }
  while(m--){
    int meret;
    cin >> meret;
    vector<int> v(meret);
    for(auto& i : v) cin >> i;
    for(int i = 1; i < meret; ++i){
      int c = lca(v[i], v[0]);
      in[v[i]].emplace(m);
      in[v[0]].emplace(m);
      out[c].emplace(m);
    }
  }
  solve(1);
  sort(begin(ans), end(ans));
  cout << ans.size() << endl;
  for(auto& i : ans){
    cout << i << " ";
  }
  cout << endl;
  return 0;
}

Compilation message (stderr)

railway.cpp: In function 'std::set<int> solve(int, int)':
railway.cpp:58:19: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |       if(a.size() >= k){
      |          ~~~~~~~~~^~~~

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