Submission #864567

#TimeUsernameProblemLanguageResultExecution timeMemory
864567iskhakkutbilimRailway (BOI17_railway)C++17
100 / 100
348 ms66876 KiB
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 2e5;
const int LOG = 20;
int up[N+1][LOG+1], depth[N+1], sub[N+1];
int bigchild[N+1], chain[N+1], Pos[N+1];
int n, m, k;
vector< pair<int, int> > edge;
vector<int> ans, g[N+1], ministr[N+1], tins[N+1];
int tin[N+1], tout[N+1], T, position;
 
 
 
 
void dfs(int v, int p){
	tin[v] = ++T;
	up[v][0] = p;
	for(int j = 1;j < LOG; j++) up[v][j] = up[up[v][j-1]][j-1];
	sub[v] = 1;
	int big=-1;
	for(auto to : g[v]){
		if(to != p){
			depth[to] = depth[v]+1;
			dfs(to, v);
			sub[v]+= sub[to];
			if(big == -1 or sub[big] < sub[to]){
				big = to;
			}
		}
	}
	tout[v] = ++T;
	bigchild[v] = big;
}
int upper(int v, int p){
	return (tin[p] <= tin[v] and tout[v] <= tout[p]);
}
void decompose(int v, int head){
	Pos[v] = ++position;
	chain[v] = head;
	if(bigchild[v] != -1){
		decompose(bigchild[v], head);
	}
	for(auto to : g[v]){
		if(to == up[v][0] or to == bigchild[v]) continue;
		decompose(to, to);
	}
}
 
int t[4*N], lazy[4*N];
 
void push(int v, int vl, int vr){
	if(lazy[v] == 0) return;
	t[v]+= (lazy[v] * (vr-vl+1));
	if(vl != vr){
		lazy[v<<1]+= lazy[v];
		lazy[v<<1|1]+= lazy[v];
	}
	lazy[v] = 0;
}
 
void add(int l, int r, int x, int v, int vl, int vr){
	push(v, vl, vr);
	if(l > vr or vl > r) return;
	if(l <= vl and r >= vr){
		lazy[v]+= x;
		push(v, vl, vr);
		return;
	}
	int mid = (vl + vr)>>1;
	add(l, r, x, v<<1, vl, mid);
	add(l, r, x, v<<1|1, mid+1, vr);
	t[v] = t[v<<1] + t[v<<1|1];
}
int get(int pos, int v, int vl, int vr){
	push(v, vl, vr);
	if(vl == vr) return t[v];
	int mid = (vl + vr)>>1;
	if(mid >= pos)  return get(pos, v<<1, vl, mid);
	else return get(pos, v<<1|1, mid+1, vr);
}
 
 
void query(int a, int b, int x){
	for(; chain[a] != chain[b]; ){
		if(depth[b] < depth[a]) swap(a, b);
		add(min(Pos[b], Pos[chain[b]]), max(Pos[b], Pos[chain[b]]), x, 1, 1, n);
		b = up[chain[b]][0];
	}	
	if(depth[b] < depth[a]) swap(a, b);
	add(min(Pos[a], Pos[b]), max(Pos[a], Pos[b]), x, 1, 1, n);
}
 
int lca(int a, int b){
	if(depth[a] > depth[b]) swap(a, b);
	if(upper(a, b)) return a;
	int k =depth[b]-depth[a];
	for(int i = 0;i < LOG; i++){
		if(k&(1LL<<i)){
			b = up[b][i];
		}
	}
	if(a == b) return a;
	for(int i = LOG-1; i >= 0; i--){
		if(up[a][i] != up[b][i]){
			a = up[a][i], b = up[b][i];
		}
	}
	return up[a][0];
}
 
main(){
   ios::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	for(int i = 1;i < n; i++){
		int a, b; cin >> a >> b;
		edge.push_back({a, b});
		g[a].push_back(b);
		g[b].push_back(a);
	}	
	dfs(1, 1);
	decompose(1, 1);
	for(int i = 1;i <= m; i++){
		int sz; cin >> sz;
		for(int j = 0;j < sz; j++){
			int idx; cin >> idx;
			ministr[i].push_back(idx);
		}
	}
	vector<int> cnt(n, 0);
	vector<int> ans;
	for(int i = 1;i <= m; i++){
		sort(all(ministr[i]), [&](int A, int B){
			return tin[A] < tin[B];	
		});
		for(int j = 0;j < ministr[i].size(); j++){
			int a = ministr[i][j], b = ministr[i][(j + 1) % (int)ministr[i].size()];
//			cout << a << ' ' << b << '\n';
			int lc = lca(a, b);
			query(a, lc, 1);
			query(b, lc, 1);
			add(Pos[lc], Pos[lc], -2, 1, 1, n);
		}
//		cout << '\n' << '\n';
	}
	for(int i = 0;i < n-1; i++){
		int a = edge[i].ff, b = edge[i].ss;
		if(tin[a] > tin[b]) swap(a, b);
		cnt[i] = get(Pos[b], 1, 1, n);
		if(cnt[i] >=2* k){
			ans.push_back(i + 1);
		}
	}
	sort(all(ans));
	cout << ans.size() << '\n';
	for(int x : ans) cout << x << ' ';
	return 0;
}

Compilation message (stderr)

railway.cpp:116:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  116 | main(){
      | ^~~~
railway.cpp: In function 'int main()':
railway.cpp:141:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |   for(int j = 0;j < ministr[i].size(); j++){
      |                 ~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...