Submission #714610

#	Time	Username	Problem	Language	Result	Execution time	Memory
714610		Iliya	Railway (BOI17_railway)	C++17	100 / 100	145 ms	27184 KiB

railway

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10, Log = 20;
vector<int> Adj[N];
vector<pair<int, int>> E;
int n, m, k, H[N], P[Log][N], ts, S[N], F[N], O[N];
void PreDFS(int v, int p) 
{
	S[v] = ++ts;
	P[0][v] = p;
	for (int i = 1; i < Log; i++) 
		P[i][v] = P[i - 1][P[i - 1][v]];
	for (int u : Adj[v]) if (u != p)
		H[u] = H[v] + 1, PreDFS(u, v);
	F[v] = ts;
}
int LCA(int u, int v)
{
	if (H[u] < H[v])
		swap(u, v);
	for (int i = 0; i < Log; i++) 
		if ((H[u] - H[v]) & (1 << i))
			u = P[i][u];
	if (u == v)
		return u;
	for (int i = Log - 1; ~i; i--)
		if (P[i][u] != P[i][v])
			u = P[i][u], v = P[i][v];
	return P[0][v];
}
void DFS(int v, int p)
{
	for (int u : Adj[v]) if (u != p)
		DFS(u, v), O[v] += O[u];
}
void Print() 
{
	for (int i = 1; i <= n; i++)
		printf("%d ", O[i]);
	puts("\n-----------------");
}
signed main() 
{
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i < n; i++) 
	{
		int u, v; scanf("%d%d", &u, &v);
		E.push_back({u, v});
		Adj[u].push_back(v);
		Adj[v].push_back(u);
	}
	PreDFS(1, 1);
	while (m--) 
	{
		int s; scanf("%d", &s);
		vector<int> V;
		for (int i = 0; i < s; i++)
		{
			int v;
			scanf("%d", &v);
			V.push_back(v);
		}
		sort(V.begin(), V.end(), [&](int a, int b){return S[a] < S[b];});
		int high = V[0];
		for (int i = 1; i < s; i++) 
		{
			int lca = LCA(V[i - 1], V[i]);
			O[lca]--, O[V[i]]++;
			if (H[lca] < H[high])
				O[high]++, O[lca]--, high = lca;
			//printf("%d %d %d %d %d %d\n", V[i - 1], V[i], lca, high, H[lca], H[high]);
			//Print();
		}
	}
	DFS(1, 1);
	int ans = 0; vector<int> res;
	for (int i = 0; i < n - 1; i++) 
	{
		if (S[E[i].first] > S[E[i].second]) 
			if (O[E[i].first] >= k)
				ans++, res.push_back(i + 1);
		if (S[E[i].first] < S[E[i].second])
			if (O[E[i].second] >= k)
				ans++, res.push_back(i + 1);
	}
	printf("%d\n", ans);
	for (int x : res)
		printf("%d ", x);
	putchar('\n');
	return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |  scanf("%d%d%d", &n, &m, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
railway.cpp:48:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   int u, v; scanf("%d%d", &u, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~
railway.cpp:56:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   int s; scanf("%d", &s);
      |          ~~~~~^~~~~~~~~~
railway.cpp:61:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |    scanf("%d", &v);
      |    ~~~~~^~~~~~~~~~

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