Submission #924615

#	Time	Username	Problem	Language	Result	Execution time	Memory
924615		KaleemRazaSyed	Railway (BOI17_railway)	C++17	100 / 100	246 ms	56448 KiB

railway

#include<iostream>
#include<vector>
#include<map>
#include<set>

using namespace std;

const int N = 1e5+5, K = 20;
int n, m, k;
vector<int> G[N];
vector<pair<int,int > > Q[N];
int in[N], out[N], sz[N], h[N], par[N][K];
int t = 0;

void pre(int v, int p = 0)
{
  par[v][0] = p;
  for(int i = 1; i < K; i++)
    par[v][i] = par[par[v][i-1]][i-1];
  
  h[v] = h[p] + 1;
  sz[v] = 1;
  in[v] = t++;
  for(int u : G[v])
    if(u != p)
      {
	pre(u, v);
	sz[v] += sz[u];
      }
  out[v] = t++;
}

int lca(int a, int b)
{
  if(h[a] < h[b]) swap(b, a);
  for(int i = K - 1; i >= 0; i--)
    if(h[par[a][i]] >= h[b])
      a = par[a][i];

  if(a == b) return a;
  for(int i = K - 1; i >= 0; i--)
    if(par[a][i] != par[b][i])
      a = par[a][i], b = par[b][i];
  return par[a][0];
}
int ans[N];
int fcnt[N];
map<int, set<int> > cnt[N];

void dfs(int v, int p = 0)
{
  int big = -1;
  for(int u : G[v])
    if(u != p)
      {
	dfs(u, v);
	big = (big == -1 ? u : sz[big] < sz[u] ? u : big);
      }
  
  for(int u : G[v])
    {
      if(u != p && u != big)
	{
	  for(auto e : cnt[u])
	    if(in[v] <= in[e.first] && out[e.first] <= out[v])
	      {
		fcnt[big] -= cnt[big][e.first].size();
		cnt[big].erase(e.first);
	      }
	    else
	      {
		fcnt[big] -= cnt[big][e.first].size();
		for(int w : e.second)
		  cnt[big][e.first].insert(w);
		fcnt[big] += cnt[big][e.first].size();
	      }
	}
    }

  if(big != -1)
    swap(cnt[big], cnt[v]), fcnt[v] = fcnt[big];

  for(auto i : Q[v])
    {
      fcnt[v] -= cnt[v][i.first].size();
      cnt[v][i.first].insert(i.second);
      fcnt[v] += cnt[v][i.first].size();
    }

  if(cnt[v].find(v) != cnt[v].end())
    {
      fcnt[v] -= cnt[v][v].size();
      cnt[v].erase(v);
    }
 
  ans[v] = fcnt[v];
}

int main()
{
  vector<pair<int,int > > e;
  cin >> n >> m >> k;
  for(int i = 1, u, v; i < n; i ++)
    {
      cin >> u >> v;
      G[u].push_back(v);
      G[v].push_back(u);
      e.push_back(make_pair(u, v));
    }
  pre(1);

  for(int i = 0; i < m; i++)
    {
      int sz;
      cin >> sz;
      vector<int> v(sz);
      for(int j = 0; j < sz; j++)
	cin >> v[j];
      
      int lc = v[0];
      for(int j = 1; j < sz; j++)
	lc = lca(lc, v[j]);

      for(int j : v)
	Q[j].push_back({lc, i});
    }

  dfs(1);
  vector<int> vec;
  for(int i = 0; i < e.size(); i++)
    {
      if(h[e[i].first] < h[e[i].second])
	swap(e[i].first, e[i].second);
      
      if(ans[e[i].first] >= k)
	vec.push_back(i + 1);
    }
  cout << vec.size() << endl;
  for(int i : vec)
    cout << i << ' ';
  cout << endl;
  return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:130:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |   for(int i = 0; i < e.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