Submission #310751

#	Time	Username	Problem	Language	Result	Execution time	Memory
310751		eggag32	Railway (BOI17_railway)	C++17	0 / 100	1093 ms	38672 KiB

railway

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl
#define debug2(x, y) debug(x), debug(y)
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))
const int mxN = 1e5 + 5;

template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }

struct seg{
	int dat[1 << 20];
	int sz;
	seg(int s){
		sz = s;
		for(int i = 0; i < (1 << 20); i++){
			dat[i] = 0;
		}
	}
	void update(int i, int s, int e, int x, int v){
		if(s == e){
			dat[i] += v;
			return;
		}
		int m = (s + e) / 2;
		if(x <= m) update(i << 1, s, m, x, v);
		else update(i << 1 | 1, m + 1, e, x, v);
		dat[i] = dat[i << 1] + dat[i << 1 | 1];
	}
	void update(int x, int v){
		update(1, 0, sz, x, v);
	}
	int query(int i, int s, int e, int x, int y){
		if(e < x || y < s) return 0;
		if(x <= s && e <= y) return dat[i];
		int m = (s + e) / 2;
		return query(i << 1, s, m, x, y) + query(i << 1 | 1, m + 1, e, x, y);
	}
	int query(int x, int y){
		return query(1, 0, sz, x, y);
	}
};

int n, m, k;
vi g[mxN];
vi ans;
vector<vi> up;
int st[mxN], fin[mxN], sta[mxN];
int num = 0, l = 1;

void dfs(int cur, int prev = 0){
	st[cur] = num++;
	up[cur][0] = prev;
	repn(i, 1, l + 1) up[cur][i] = up[up[cur][i - 1]][i - 1];
	for(int x : g[cur]) if(x != prev) dfs(x, cur);
	fin[cur] = num++;
}

bool upper(int a, int b){
	return st[a] <= st[b] && fin[a] >= fin[b];
}

int lca(int a, int b){
	if(upper(a, b)) return a;
	if(upper(b, a)) return b;
	for(int i = l; i >= 0; i--) if(!upper(up[a][i], b)) a = up[a][i];
	return up[a][0];
}

map<pi, int> ind;

void dfs1(int cur, int prev){
	for(int x : g[cur]) if(x != prev){
		dfs1(x, cur);
		sta[cur] += sta[x];
	}
	if(sta[cur] >= k && prev != -1) ans.pb(ind[mp(cur, prev)]);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	cin >> n >> m >> k;
	rep(i, n - 1){
		int a, b;
		cin >> a >> b;
		a--, b--;
		ind[mp(a, b)] = ind[mp(b, a)] = i;
		g[a].pb(b);
		g[b].pb(a);
	}
	up.resize(n + 1);
	while((1 << l) <= n) l++;
	rep(i, n) up[i].resize(l + 1);
	dfs(0);
	seg tree(num);
	rep(i, m){
		int s;
		cin >> s;
		int lc;
		vi nw(s, 0);
		map<int, int> p;
		rep(j, s){
			cin >> nw[j];
			nw[j]--;
			p[nw[j]] = 1;
			if(!j) lc = nw[j];
			else lc = lca(lc, nw[j]);
		}
		rep(j, s) if(nw[j] != lc) sta[nw[j]]++;
		rep(j, s) tree.update(st[nw[j]], 1);
		vi vis(s, 0);
		rep(j, s){
			int a = nw[j];
			for(int k = l; k >= 0; k--){
				int nxt = up[a][k];
				int nm = tree.query(st[nxt], fin[nxt]) - tree.query(st[nw[j]], fin[nw[j]]);
				if(!nm) a = up[a][k];
			}
			int nxt = up[a][0];
			int nm = tree.query(st[nxt], fin[nxt]) - tree.query(st[nw[j]], fin[nw[j]]);
			int nm1 = tree.query(st[a], fin[a]) - tree.query(st[nw[j]], fin[nw[j]]);
			if(nm && !nm1){
				tree.update(st[nw[j]], -1);
				vis[j] = 1;
				sta[nxt]--;
				if(p[nxt]) sta[nxt]--;
			}
		}
		rep(j, s) if(!vis[j]) tree.update(j, -1);
	}
	dfs1(0, -1);
	cout << (int)(ans.size()) << endl;
	sort(all(ans));
	for(int x : ans) cout << x + 1 << " ";
	cout << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/

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