Submission #915421

#	Time	Username	Problem	Language	Result	Execution time	Memory
915421		starchan	Railway (BOI17_railway)	C++17	100 / 100	150 ms	73148 KiB

railway

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
#define MX (int)3e5+5
#define LOGM (int)18
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
vector<int> adj[MX];
vector<in> edges;
int pa[LOGM][MX];
int tin[MX];
int tout[MX];
int focus[MX];
int timer = 0;
int label[MX];

void dfs(int u, int p)
{
	pa[0][u] = p;
	tin[u] = ++timer;
	for(int v: adj[u])
	{
		if(v==p)
			continue;
		dfs(v, u);
	}
	tout[u] = timer;
	return;
}

int lca(int u, int v)
{
	if(tin[u] > tin[v])
		swap(u, v);
	if((tout[u] >= tout[v]))
		return u;
	for(int i = LOGM-1; i >= 0; i--)
	{
		if(tout[pa[i][u]] < tout[v])
			u = pa[i][u];
	}
	return pa[0][u];
}

void dfs2(int u, int p)
{
	for(int v: adj[u])
	{
		if(v==p)
			continue;
		dfs2(v, u);
		focus[u]+=focus[v];
	}
	return;
}

signed main()
{
	fast();
	int n, q, k;
	cin >> n >> q >> k;
	
	int m = n-1;
	while(m--)
	{
		int u, v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
		edges.pb({u, v});
	}

	dfs(1, 0);
	int curr = 0;
	for(auto [x, y]: edges)
	{
		if(tin[x] >= tin[y])
			swap(x, y);
		label[y] = ++curr;
	}

	pa[0][0] = 0;
	tout[0] = INF;
	for(int i = 1; i < LOGM; i++)
	{
		for(int j = 0; j <= n; j++)
			pa[i][j] = pa[i-1][pa[i-1][j]];
	}
	while(q--)
	{
		int M;
		cin >> M;
		vector<in> v;
		for(int QoIGn = 1; QoIGn <= M; QoIGn++)
		{
			int u;
			cin >> u;
			focus[u]++;
			v.pb({tin[u], u});
		}
		sort(v.begin(), v.end());
		for(int i = 0; i < v.size(); i++)
			focus[lca(v[i].s, v[(i+1)%M].s)]--;
	}
	/*cout << "printign tin[u], tout[u]" << endl;
	for(int u = 1; u <= n; u++)
	{
		printf("tin[%d] = %d, tout[%d] = %d", u, tin[u], u, tout[u]);
		cout << endl;
	}
	cout << "printing lcas NIGELTS" << endl;
	for(int i = 2; i <= n; i++)
	{
		for(int j = i+1; j <= n; j++)
		{
			printf("lca(%d, %d) = %d", i, j, lca(i, j));
			cout << endl;
		}
	}*/
	dfs2(1, 0);
	int cnt = 0;
	vector<int> DOFINQ;
	for(int i = 2; i <= n; i++)
	{
		if(focus[i] >= k)
			DOFINQ.pb(label[i]);
	}
	sort(DOFINQ.begin(), DOFINQ.end());
	cout << DOFINQ.size() << "\n";
	for(int ttt: DOFINQ)
		cout << ttt << " ";
	return 0;
}	

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:107:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |   for(int i = 0; i < v.size(); i++)
      |                  ~~^~~~~~~~~~
railway.cpp:126:6: warning: unused variable 'cnt' [-Wunused-variable]
  126 |  int cnt = 0;
      |      ^~~

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