Submission #383253

#	Time	Username	Problem	Language	Result	Execution time	Memory
383253		ritul_kr_singh	Railway (BOI17_railway)	C++17	100 / 100	606 ms	35936 KiB

railway

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << " " <<
#define nl << "\n"

struct segtree{
	int sz = 1;
	vector<bool> a;
	segtree(int n){
		while(sz < n) sz *= 2;
		a.assign(2*sz, false);
	}
	void update(int i, int x, int lx, int rx){
		if(rx-lx==1) return void(a[x] = !a[x]);
		int mx = (lx+rx)/2;
		if(i<mx) update(i, 2*x+1, lx, mx);
		else update(i, 2*x+2, mx, rx);
		a[x] = max(a[2*x+1], a[2*x+2]);
	}
	void update(int i){ update(i, 0, 0, sz); }
	bool get(int l, int r, int x, int lx, int rx){
		if(r<=lx or rx<=l) return false;
		if(l<=lx and rx<=r) return a[x];
		int mx = (lx+rx)/2;
		return get(l, r, 2*x+1, lx, mx) or get(l, r, 2*x+2, mx, rx);
	}
	bool get(int l, int r){ return get(l, r+1, 0, 0, sz); }
};

vector<vector<pair<int, int>>> g;
vector<array<int, 18>> p;
vector<int> t0, t1, dp, ans;
int dfsTimer = 0;

void dfs0(int u, int parent){
	t0[u] = dfsTimer++;
	p[u][0] = parent;
	for(int i=1; i<18; ++i) p[u][i] = p[p[u][i-1]][i-1];
	for(auto e : g[u]) if(e.first != parent) dfs0(e.first, u);
	t1[u] = dfsTimer++;
}

bool isAncestor(int u, int v){
	return t0[u]<=t0[v] and t1[v]<=t1[u];
}

int dfs1(int u){
	for(auto edge : g[u]){
		int v = edge.first, e = edge.second;
		if(v==p[u][0]) continue;
		ans[e] = dfs1(v);
		dp[u] += ans[e];
	}
	return dp[u];
}

int lca(int u, int v){
	if(isAncestor(u, v)) return u;
	for(int i=17; i>=0; --i)
		while(u and !isAncestor(p[u][i], v)) u = p[u][i];
	return p[u][0];
}

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, m, k, x, y; cin >> n >> m >> k;
	g.resize(n), p.resize(n), t0.resize(n), t1.resize(n);
	dp.assign(n, 0), ans.resize(n);
	for(int i=1; i<n; ++i){
		cin >> x >> y; --x, --y;
		g[x].emplace_back(y, i);
		g[y].emplace_back(x, i);
	}
	dfs0(0, 0);
	segtree st(n+n);
	while(m--){
		int s; cin >> s;
		vector<int> curr(s), updated;
		for(int &i : curr) cin >> i, --i;
		int x = curr[0];
		for(int i : curr) x = lca(x, i);

		for(int i : curr){
			int u = i;
			if(st.get(t0[u], t1[u])) continue;
			for(int j=17; j>=0; --j)
				while(u and isAncestor(x, p[u][j]) and !st.get(t0[p[u][j]], t1[p[u][j]]))
					u = p[u][j];
			st.update(t0[i]);
			updated.push_back(t0[i]);
			++dp[i];
			if(u != x) u = p[u][0];
			--dp[u];
		}
		for(int i : updated) st.update(i);
	}
	dfs1(0);
	vector<int> res;
	for(int i=1; i<n; ++i) if(ans[i]>=k) res.push_back(i);
	// for(int i : ans) cout << i << ' ';
	// cout nl;
	cout << res.size() nl;
	for(int i : res) cout << i << ' ';	
}

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