Submission #547650

#	Time	Username	Problem	Language	Result	Execution time	Memory
547650		nafis_shifat	Railway (BOI17_railway)	C++17	100 / 100	108 ms	27636 KiB

railway

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=1e5+5;
const int inf=1e9;
int n, m, k;
vector<int> adj[mxn];
int in[mxn];
int out[mxn];
int T = 0;
int pa[20][mxn];
int level[mxn] = {};
int val[mxn] = {};
int l[mxn], r[mxn];
vector<int> ans;
void initLCA() {
	for(int i = 1;i < 18; i++)
		for(int j = 1;j <= n; j++)
			pa[i][j] = pa[i - 1][pa[i - 1][j]];
}


int findLCA(int u,int v) {

	if(level[u] < level[v]) swap(u,v);
	int diff = level[u] - level[v];
	for(int i = 0;i < 18; i++) if((diff>>i)&1) u = pa[i][u];
	if(u == v) return u;
	for(int i = 17;i >= 0; i--) {
		if(pa[i][u] != pa[i][v]){
			u = pa[i][u];
			v = pa[i][v];
		}
	}
	return pa[0][u];
}
void dfs0(int u, int prev) {
	in[u] = ++T;
	pa[0][u] = prev;
	level[u] = level[prev] + 1;
	for(int i : adj[u]) {
		int v = l[i] ^ r[i] ^ u;
		if(v == prev) continue;
		dfs0(v, u);
	}
	out[u] = T;
}

void dfs(int u, int prev) {
	for(int i : adj[u]) {
		int v = l[i] ^ r[i] ^ u;
		if(v == prev) continue;
		dfs(v, u);

		if(val[v] >= k) ans.push_back(i);
		val[u] += val[v];
	}
}
int main() {
	cin >> n >> m >> k;

	for(int i = 1; i < n; i++) {
		scanf("%d%d", &l[i], &r[i]);
		adj[l[i]].push_back(i);
		adj[r[i]].push_back(i);
	}

	dfs0(1, 0);
	initLCA();

	for(int i = 1; i <= m; i++) {
		int s;
		scanf("%d", &s);
		vector<int> con;
		for(int j = 1; j <= s; j++) {
			int x;
			scanf("%d", &x);
			con.push_back(x);
		}

		sort(con.begin(), con.end(), [](int a, int b) {
			return in[a] < in[b];
		});


		for(int i = 1; i < s; i++) {
			con.push_back(findLCA(con[i], con[i - 1]));
		}

		sort(con.begin(), con.end());
		con.erase(unique(con.begin(), con.end()), con.end());

		sort(con.begin(), con.end(), [](int a, int b) {
			return in[a] < in[b];
		});

		stack<int> st;

		st.push(con[0]);

		for(int i = 1; i < con.size(); i++) {
			while(!st.empty() && out[st.top()] < in[con[i]]) st.pop();
			val[con[i]]++;
			val[st.top()]--;
			
			st.push(con[i]);

		}

	}

	dfs(1, 0);
	sort(ans.begin(), ans.end());

	cout<<ans.size()<<endl;

	for(int i : ans) cout<<i<<" ";
	
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:102:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |   for(int i = 1; i < con.size(); i++) {
      |                  ~~^~~~~~~~~~~~
railway.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |   scanf("%d%d", &l[i], &r[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
railway.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |   scanf("%d", &s);
      |   ~~~~~^~~~~~~~~~
railway.cpp:78:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |    scanf("%d", &x);
      |    ~~~~~^~~~~~~~~~

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