Submission #920635

#	Time	Username	Problem	Language	Result	Execution time	Memory
920635		BBart888	Railway (BOI17_railway)	C++14	0 / 100	161 ms	70084 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 = 2e5 + 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;
int dp[MAXN];
set<int> zawiadowca[MAXN];
vector<int> answer;
set<int> zabierz[MAXN];

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


void check(int v, int p)
{
	
	for (auto u : adj[v])
	{
		if (u.first == p)
			continue;
		check(u.first, v);
		//cout <<v<<" => "<< u.first << " " << add[u.first] << '\n';
		if (zawiadowca[u.first].size() >= k)
		{
			answer.push_back(u.second);
			//cout << u.second << '\n';
		}
		
		if (zawiadowca[u.first].size() > zawiadowca[v].size())
		{
			swap(zawiadowca[u.first], zawiadowca[v]);
		}
		for (auto x : zawiadowca[u.first])
			zawiadowca[v].insert(x);
	}
	
	for (auto x : zabierz[v])
		if (zawiadowca[v].find(x) != zawiadowca[v].end())
			zawiadowca[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 v;
		vector<int> important;
		cin >> v;
		int lc = v;
		important.push_back(v);
		for (int f = 1; f < s; f++)
		{
			cin >> v;
			lc = lca(lc, v);
			important.push_back(v);
		}
		 
		for (int f = 0; f < s; f++)
		{
			zawiadowca[important[f]].insert(i+1);
		}
		zabierz[lc].insert(i+1);

	}

	
	
	check(1, 1);

	cout << answer.size() << '\n';

	for (auto x : answer)
		cout << x << " ";










	return 0;
}

Compilation message (stderr)

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

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