Submission #864532

#	Time	Username	Problem	Language	Result	Execution time	Memory
864532		iskhakkutbilim	Railway (BOI17_railway)	C++17	52 / 100	238 ms	118252 KiB

railway

#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);
			tins[i].push_back(tin[idx]);
		}
		sort(all(tins[i]));
	}
	vector<int> cnt(n, 0);
	vector<int> ans;
	if(n <= 10000 && m <= 2000){
		for(int i = 1;i <= m; i++){
			for(int j = 0;j < n-1; j++){
				int a = edge[j].ff, b = edge[j].ss;
				if(tin[a] > tin[b]) swap(a, b);
				int it = lower_bound(all(tins[i]), tin[b]) - tins[i].begin();
				if(it >= tins[i].size() or tins[i][it] > tout[b]) continue;
				if(tins[i][0] < tin[b] or tins[i].back() > tout[b]){
					cnt[j]++;
				}
			}
		}
		for(int i = 0;i < n; i++){
			if(cnt[i] >= k){
				ans.push_back(i + 1);
			}
		}
	}else{
		for(int i = 1;i <= m; i++){
			if(ministr[i].size() != 2) assert(false);
			int a = ministr[i][0], b = ministr[i][1];
			int lc = lca(a, b);
			query(a, lc, 1);
			query(b, lc, 1);
			add(Pos[lc], Pos[lc], -2, 1, 1, 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] >= 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:145:11: 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]
  145 |     if(it >= tins[i].size() or tins[i][it] > tout[b]) continue;
      |        ~~~^~~~~~~~~~~~~~~~~

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