Submission #920647

#	Time	Username	Problem	Language	Result	Execution time	Memory
920647		BBart888	Railway (BOI17_railway)	C++14	100 / 100	192 ms	88404 KiB

railway

#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <queue>
#include <stack>
#include <cassert>
#include <cstring>
#include <climits>
#include <functional>
#include <cstdlib>
#include <complex>
#include <array>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <random>
#define fileIO(name) if(fopen(name".in", "r")) {freopen(name".in", "r", stdin); freopen(name".out", "w", stdout);}



using namespace std;
const int MAXN = 4e5 + 111;
using ll = long long;
const int P = 31;
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;
using ld = long double;
const ld EPS = 1e-5;
using pii = pair<int, int>;
typedef complex<ll> Point;
const int K = 600;


int n, m, k;
vector<pair<int,int>> adj[MAXN];
int up[MAXN][20];
int tin[MAXN];
int tout[MAXN];
vector<pair<int, int>> edges;
int timer;
vector<int> add[MAXN];
vector<int> rem[MAXN];
set<int> answer;



void dfs(int v, int p)
{
	tin[v] = ++timer;
	up[v][0] = p;
	for (int i = 1; i < 20; i++)
		up[v][i] = up[up[v][i - 1]][i - 1];
	for (auto u : adj[v])
	{
		if (u.first == p)
			continue;
		dfs(u.first, v);
	}
	tout[v] = ++timer;
}


bool is_ancestor(int u, int v)
{
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}


int lca(int a, int b)
{
	if (is_ancestor(a, b))
		return a;
	if (is_ancestor(b, a))
		return b;
	for (int i = 19; i >= 0; i--)
	{
		if (!is_ancestor(up[a][i], b))
			a = up[a][i];
	}
	return up[a][0];
}

set<int> vals[MAXN];

void check(int v, int p)
{
	int big = v;
	for (auto u : adj[v])
	{
		if (u.first == p)
			continue;
		check(u.first, v);
		if (vals[u.first].size() > vals[big].size())
			big = u.first;
		if (vals[u.first].size() >= k)
			answer.insert(u.second);
	}
	swap(vals[v], vals[big]);
	for (auto x : adj[v])
	{
		if (x.first == p)
			continue;
		for (auto vv : vals[x.first])
			vals[v].insert(vv);
	}
	for (auto x : add[v])
		vals[v].insert(x);
	for (auto x : rem[v])
		vals[v].erase(x);
}



int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	//fileIO("cardgame");

	cin >> n >> m >> k;

	for (int i = 1; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		adj[a].push_back({ b ,i});
		adj[b].push_back({ a ,i});
		edges.push_back({ a,b });
	}

	dfs(1, 1);

	for (int i = 0; i < m; i++)
	{
		int s;
		cin >> s;
		
		int y = 0;
		vector<int> vertices;
		for (int j = 0; j < s; j++)
		{
			int x;
			cin >> x;
			vertices.push_back(x);
			y = (y == 0 ? x : lca(y, x));
		}
		rem[y].push_back(i + 1);
		for (int j = 0; j < s; j++)
			add[vertices[j]].push_back(i + 1);
	}

	check(1, 1);

	cout << answer.size() << '\n';
	for (auto x : answer)
		cout << x << " ";
	
	cout << '\n';









	return 0;
}

Compilation message (stderr)

railway.cpp: In function 'void check(int, int)':
railway.cpp:102:28: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  102 |   if (vals[u.first].size() >= k)
      |       ~~~~~~~~~~~~~~~~~~~~~^~~~

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