Submission #1108954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108954		FanOfWilliamLin	Railway (BOI17_railway)	C++14	100 / 100	69 ms	26980 KiB

railway

#include <bits/stdc++.h>
using namespace std;
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template <class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//- insert(x),erase(x)
//- find_by_order(k): return iterator to the k-th smallest element
//- order_of_key(x): the number of elements that are strictly smaller

#define ll long long
#define ld long double
#define ar array
#define vt vector
#define pb push_back
#define bit(i, x) ((x>>i)&1ULL)
#define pf push_front
#define all(v) v.begin(), v.end()
#define lla(v) v.rbegin(), v.rend()

/*mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
    return uniform_int_distribution<ll> (l, r)(rng); 
}*/

const int mxN=1e5+5;
const int LG=21;
int n, m, k, timer=0;
int tin[mxN], tout[mxN], bit[mxN], depth[mxN], up[mxN][LG], edge[mxN];
vt<pair<int, int>> adj[mxN];

void dfs(int u=1) {
	tin[u]=++timer;
	for(pair<int, int> ele: adj[u]) {
		int v=ele.first;
		int ii=ele.second;
		if(v==up[u][0]) {
			continue;
		}
		up[v][0]=u;
		depth[v]=depth[u]+1;
		edge[v]=ii;
		for(int i=1; i<LG; ++i) {
			up[v][i]=up[up[v][i-1]][i-1];
		}
		dfs(v);
	}
	tout[u]=timer;
}

int lca(int u, int v) {
	if(depth[u]!=depth[v]) {
		if(depth[u]<depth[v]) {
			swap(u, v);
		}
		int k=depth[u]-depth[v];
		for(int i=LG-1; i>=0; --i) {
			if(bit(i, k)) {
				u=up[u][i];
			}
		}
	}
	if(u==v) {
		return u;
	}
	for(int i=LG-1; i>=0; --i) {
		if(up[u][i]!=up[v][i]) {
			u=up[u][i];
			v=up[v][i];
		}
	}
	return up[u][0];
}

void upd(int idx, int val) {
	for(; idx<=mxN; idx+=(idx&(-idx))) {
		bit[idx]+=val;
	}
}

int qury(int l, int r) {
	int res=0;
	for(; r>0; r-=(r&(-r))) {
		res+=bit[r];
	}
	if(l-1==0) {
		return res;
	}
	for(--l; l>0; l-=(l&(-l))) {
		res-=bit[l];
	}
	return res;
}

void solve() {
	//solve here
	cin >> n >> m >> k;
	for(int i=1; i<=n-1; ++i) {
		int u, v;
		cin >> u >> v;
		adj[u].pb({v, i});
		adj[v].pb({u, i});
	}
	dfs();
	for(int ii=0; ii<m; ++ii) {
		int sz;
		cin >> sz;
		vt<int> vec;
		for(int i=0; i<sz; ++i) {
			int aa;
			cin >> aa;
			vec.pb(aa);
		}
		sort(all(vec), [&](int A, int B) {
			return tin[A]<tin[B];
		});
		for(int i=1; i<sz; ++i) {
			int l=lca(vec[i-1], vec[i]);
			upd(tin[vec[i-1]], 1);
			upd(tin[vec[i]], 1);
			upd(tin[l], -2);
		}
		int l=lca(vec[sz-1], vec[0]);
		upd(tin[vec[sz-1]], 1);
		upd(tin[vec[0]], 1);
		upd(tin[l], -2);
	}
	vt<int> ans;
	for(int i=2; i<=n; ++i) {
		if(qury(tin[i], tout[i])>=2*k) {
			ans.pb(edge[i]);
		}
	}
	sort(all(ans));
	cout << ans.size() << "\n";
	for(auto& ele: ans) {
		cout << ele << " ";
	}
	cout << "\n";
}
 
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	//freopen("template.inp", "r", stdin);
	//freopen("template.out", "w", stdout);	

	int TC=1;
	//cin >> TC;
	while(TC--) {
		solve();
	}
}

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