Submission #825269

#	Time	Username	Problem	Language	Result	Execution time	Memory
825269		QwertyPi	Railway (BOI17_railway)	C++14	100 / 100	207 ms	26396 KiB

railway

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 11;

vector<pair<int, int>> G[MAXN];
int op[MAXN], ed[MAXN], t = 0;
int anc[20][MAXN], dep[MAXN], ps[MAXN], id[MAXN];

void dfs(int v, int pa = -1){
	op[v] = ++t;
	for(auto [u, e] : G[v]){
		if(u != pa){
			id[u] = e; anc[0][u] = v; for(int j = 1; j < 20; j++) anc[j][u] = anc[j - 1][anc[j - 1][u]];
			dep[u] = dep[v] + 1;
			dfs(u, v);
		}
	}
	ed[v] = t;
}

void dfs_calc(int v, int pa = -1){
	for(auto [u, e] : G[v]){
		if(u == pa) continue;
		dfs_calc(u, v);
		ps[v] += ps[u];
	}
}

bool is_anc(int u, int v){
	return op[u] <= op[v] && ed[v] <= ed[u];
}

int kth_anc(int u, int k){
	for(int j = 19; j >= 0; j--){
		if((1 << j) & k) u = anc[j][u];
	}
	return u;
}

int lca(int u, int v){
	if(dep[u] < dep[v]) swap(u, v);
	u = kth_anc(u, dep[u] - dep[v]);
	for(int j = 19; j >= 0; j--){
		if(anc[j][u] != anc[j][v]){
			u = anc[j][u];
			v = anc[j][v];
		}
	}
	return u == v ? u : anc[0][u];
}

int32_t main(){
	int n, m, k; cin >> n >> m >> k;
	for(int i = 0; i < n - 1; i++){
		int u, v; cin >> u >> v;
		G[u].push_back({v, i + 1});
		G[v].push_back({u, i + 1});
	}
	dfs(1);
	for(int i = 0; i < m; i++){
		int k; cin >> k; vector<int> V;
		for(int j = 0; j < k; j++){
			int u; cin >> u; V.push_back(u);
		}
		sort(V.begin(), V.end(), [](int u, int v){ return op[u] < op[v]; });

		vector<int> st {};
		for(int i = 0; i < V.size(); i++){
			int v = V[i];
			if(st.empty() || is_anc(st.back(), v)){
				st.push_back(v);
				continue;
			}
			while(st.size() >= 2 && !is_anc(st[st.size() - 2], v)){
				ps[st[st.size() - 1]]++; ps[st[st.size() - 2]]--;
				st.pop_back();
			}
			int l = lca(st.back(), v);
			ps[st.back()]++; ps[l]--;
			if(st.size() >= 2 && st[st.size() - 2] == l){
				st.pop_back(); st.push_back(v);
			}else{
				st.pop_back(); st.push_back(l); st.push_back(v);
			}
		}
		ps[st.back()]++; ps[st.front()]--;
	}
	dfs_calc(1);
	vector<int> ans;
	for(int i = 2; i <= n; i++){
		if(ps[i] >= k) ans.push_back(id[i]);
	}
	sort(ans.begin(), ans.end());

	cout << ans.size() << endl;
	for(auto i : ans) cout << i << ' '; cout << endl;
}

Compilation message (stderr)

railway.cpp: In function 'void dfs(int, int)':
railway.cpp:12:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   12 |  for(auto [u, e] : G[v]){
      |           ^
railway.cpp: In function 'void dfs_calc(int, int)':
railway.cpp:23:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |  for(auto [u, e] : G[v]){
      |           ^
railway.cpp: In function 'int32_t main()':
railway.cpp:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   for(int i = 0; i < V.size(); i++){
      |                  ~~^~~~~~~~~~
railway.cpp:97:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   97 |  for(auto i : ans) cout << i << ' '; cout << endl;
      |  ^~~
railway.cpp:97:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   97 |  for(auto i : ans) cout << i << ' '; cout << endl;
      |                                      ^~~~

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