Submission #291323

#	Time	Username	Problem	Language	Result	Execution time	Memory
291323		someone_aa	Railway (BOI17_railway)	C++17	100 / 100	427 ms	44912 KiB

railway

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll, ll>
#define sz(x) int(x.size())
using namespace std;
const int maxn = 100100;
const int maxlog = 20;
vector<int>g[maxn];
vector<int>gt[maxn];
ll n, q, k;

int opent[maxn], euler[maxn];
int sbtsize[maxn], br;
int depth[maxn];

int parent[maxn][maxlog];

void dfs_preprocess(int node, int p, int d) {
	opent[node] = br;
	euler[br] = node;
	sbtsize[node] = 1;
	depth[node] = d;
	br++;

	parent[node][0] = p;

	for(int i:g[node]) {
		if(i == p) continue;

		dfs_preprocess(i, node, d + 1);
		sbtsize[node] += sbtsize[i];
	}
}

void lca_preprocess() {
	for(int level=1;level<maxlog;level++) {
		for(int i=1;i<=n;i++) {
			if(parent[i][level-1] == -1) continue;
			parent[i][level] = parent[parent[i][level-1]][level-1];
		}
	}
}

int lca(int a, int b) {
	if(depth[a] > depth[b]) swap(a, b);
	if(opent[b] >= opent[a] && opent[b] < opent[a] + sbtsize[a]) return a;

	for(int i=maxlog-1;i>=0;i--) {
		if(parent[a][i] == -1) continue;

		int nextnode = parent[a][i];
		if(opent[b] < opent[nextnode] || opent[b] >= opent[nextnode] + sbtsize[nextnode]) a = nextnode;
	}

	return parent[a][0];
}

int start_here[maxn], end_here[maxn];
map<pii, int> ind;
vector<int>result;

int dfs_count(int node, int p) {
	int sum = 0;
	for(int i:g[node]) {
		if(i == p) continue;

		int tmp = dfs_count(i, node);
		if(tmp >= k) {
			result.pb(ind[mp(i, node)]);
		}

		sum += tmp;
	}

	return sum + start_here[node] - end_here[node];
} 


int main() {
	cin>>n>>q>>k;

	ll u, v;
	for(int i=0;i<n-1;i++) {
		cin>>u>>v;
		g[u].pb(v);
		g[v].pb(u);

		ind[mp(u, v)] = ind[mp(v, u)] = i + 1;
	}

	memset(parent, -1, sizeof(parent));
	dfs_preprocess(1, -1,0);
	lca_preprocess();

	int s;
	bool root;
	while(q--) {
		cin>>s;

		vector<pii> v;
		set<int>st;
		for(int i=0;i<s;i++) {
			cin>>u;
			v.pb(mp(opent[u], u));
			st.insert(u);

		}

		sort(v.begin(), v.end());
		for(int i=1;i<sz(v);i++) {
			st.insert(lca(v[i].second, v[i-1].second));
		}

		v.clear();
		for(int i:st) {
			v.pb(mp(opent[i], i));
		}		sort(v.begin(), v.end());

		stack<int>node_stack;
		node_stack.push(v[0].second);
		for(int i=1;i<sz(v);i++) {

			while(!node_stack.empty()) {
				int curr = node_stack.top();
				int nextnode = v[i].second;

				if(opent[nextnode] >= opent[curr] && opent[nextnode] < opent[curr] + sbtsize[curr]) {
					start_here[nextnode]++;
					end_here[curr]++;
					node_stack.push(nextnode);
					break;
				}
				else {
					node_stack.pop();
				}
			}
		}
	}

	dfs_count(1, -1);
	sort(result.begin(), result.end());
	cout<<sz(result)<<"\n";
	for(int i:result) {
		cout<<i<<" ";
	} cout<<"\n";
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:99:7: warning: unused variable 'root' [-Wunused-variable]
   99 |  bool root;
      |       ^~~~

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