Submission #765279

#	Time	Username	Problem	Language	Result	Execution time	Memory
765279		Meloric	Railway (BOI17_railway)	C++14	100 / 100	139 ms	40296 KiB

railway

#include <bits/stdc++.h>
#define pb push_back
#define int int64_t
#define pii pair<int, int>
#define X first
#define Y second
#define all(x) (x).begin(),(x).end()
#define lb lower_bound
#define ub upper_bound

using namespace std;

const int inf = 1e18;

void p(auto A){
	for(auto e : A)cout << e << ' ';
	cout << '\n';
}
void solve(){
	int n, m, k; cin >> n >> m >> k;
	vector<vector<pii>> g(n);
	for(int i = 1; i< n; i++){
		int c, d; cin >> c >> d; c--; d--;
		g[c].pb({d, i});
		g[d].pb({c, i});
	}
	int lg = 25;
	vector<int>pre(n),pst(n);
	vector<vector<int>> up(n, vector<int>(lg));
	int t = 0;
	
	auto dfs = [&](auto&& self, int u, int p)->void{
		pre[u] = t++;
		up[u][0] = p;
		for(int i = 1; i< lg; i++)up[u][i] = up[up[u][i-1]][i-1];
		for(auto [v, _] : g[u])if(v!=p){
			self(self, v, u);
		}
		pst[u] = t++;
	};
	dfs(dfs, 0, 0);
	

	auto anc = [&](int a, int b)->bool{
		if(pre[a] <= pre[b] && pst[a] >= pst[b])return true;
		return false;
	};
	
	auto lca = [&](int a, int b)->int{
		if(anc(a, b))return a;
		if(anc(b, a))return b;
		for(int i = lg-1; i>= 0; i--)if(!anc(up[a][i], b))a=up[a][i];
		return up[a][0];
	};
	
	vector<int> A(n);
	for(int i = 0; i< m; i++){
		int c; cin >> c;
		vector<int> tmp;
		for(int i = 0; i< c; i++){
			int d; cin >> d; d--;
			tmp.pb(d);
		}

		sort(all(tmp), [&](int a, int b){return pre[a] < pre[b];});
		for(auto e : tmp)A[e]++;
		for(int j = 1; j< c; j++)A[lca(tmp[j], tmp[j-1])]--;
		A[lca(tmp.front(), tmp.back())]--;

	}
	
	vector<int> ans(n);
	auto dfs2 = [&](auto&& self, int u, int p)->void{
		for(auto [v, id] : g[u])if(v!=p){
			self(self, v, u);
			ans[id] = A[v];
			A[u]+=A[v];
		}
	};

	dfs2(dfs2, 0, 0);
	int num = 0;
	for(auto e : ans)if(e >= k)num++;
	cout << num << '\n';
	for(int i =1; i< n; i++)if(ans[i] >= k)cout << i << ' ';
}
		
	
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int t = 1;
	//cin >> t;
	while(t--)solve();
}

Compilation message (stderr)

railway.cpp:15:8: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   15 | void p(auto A){
      |        ^~~~
railway.cpp: In lambda function:
railway.cpp:36:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |   for(auto [v, _] : g[u])if(v!=p){
      |            ^
railway.cpp: In lambda function:
railway.cpp:74:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   74 |   for(auto [v, id] : g[u])if(v!=p){
      |            ^

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