Submission #134257

#	Time	Username	Problem	Language	Result	Execution time	Memory
134257		Kastanda	Railway (BOI17_railway)	C++11	100 / 100	190 ms	22256 KiB

railway

#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
using namespace std;
const int N = 100005, LG = 17;
int n, q, k, ts, A[N], st[N], en[N], H[N], P[N][LG], R[N];
vector < pair < int , int > > Adj[N];
void DFS(int v, int p)
{
	st[v] = ts ++;
	P[v][0] = p;
	for (int i = 1; i < LG; i++)
		P[v][i] = P[P[v][i - 1]][i - 1];
	for (auto &u : Adj[v])
		if (u.x != p)
			H[u.x] = H[v] + 1, DFS(u.x, v);
	en[v] = ts;
}
inline int LCA(int v, int u)
{
	if (H[v] < H[u])
		return (LCA(u, v));
	for (int i = 0; i < LG; i++)
		if ((H[v] - H[u]) & (1 << i))
			v = P[v][i];
	if (v == u)
		return (v);
	for (int i = LG - 1; ~ i; i --)
		if (P[v][i] != P[u][i])
			v = P[v][i], u = P[u][i];
	return (P[v][0]);
}
inline bool CMP(int i, int j)
{
	return (st[i] < st[j]);
}
void FNL(int v, int id)
{
	for (auto &u : Adj[v])
		if (u.y != id)
		{
			FNL(u.x, u.y);
			A[v] += A[u.x];
		}
	R[id] = A[v];
}
int main()
{
	scanf("%d%d%d", &n, &q, &k);
	for (int i = 1; i < n; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		Adj[a].pb({b, i});
		Adj[b].pb({a, i});
	}
	DFS(1, 0);
	for (int i = 1; i <= q; i++)
	{
		int m;
		scanf("%d", &m);
		vector < int > vec(m);
		for (int j = 1; j <= m; j++)
			scanf("%d", &vec[j - 1]);
		sort(vec.begin(), vec.end(), CMP);
		for (int j = 0; j < m; j++)
			vec.pb(LCA(vec[j], vec[(j + 1) % m]));
		sort(vec.begin(), vec.end(), CMP);
		vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
		if ((int)vec.size() <= 1)
			continue;
		vector < int > stk; stk.pb(vec[0]);
		for (int j = 1; j < (int)vec.size(); j++)
		{
			while (stk.size() && en[stk.back()] < en[vec[j]])
				stk.pop_back();
			A[vec[j]] ++;
			A[stk.back()] --;
			stk.pb(vec[j]);
		}
	}
	FNL(1, 0);
	vector < int > vec;
	for (int i = 1; i < n; i++)
		if (R[i] >= k)
			vec.pb(i);
	printf("%d\n", (int)vec.size());
	for (int id : vec)
		printf("%d ", id);
	return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &q, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
railway.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
railway.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &m);
   ~~~~~^~~~~~~~~~
railway.cpp:65:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &vec[j - 1]);
    ~~~~~^~~~~~~~~~~~~~~~~~~

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