Submission #713931

#	Time	Username	Problem	Language	Result	Execution time	Memory
713931		study	Railway (BOI17_railway)	C++17	100 / 100	328 ms	47604 KiB

railway

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5;

vector<int> adj[N];
int in[N], out[N], segt[2*N],pere[20][N], depth[N];
map<int,int> id;
bitset<N> vu;

int timer = 0;

void dfs(int node = 0, int d = 0){
	vu[node] = true;
	in[node] = timer;
	depth[node] = d;
	timer++;
	for (int i:adj[node]){
		if (!vu[i]){
			pere[0][i] = node;
			dfs(i,d+1);
		}
	}
	out[node] = timer;
}

void modify(int node, int val){
	node += N;
	segt[node] += val;
	node >>= 1;
	while (node){
		segt[node] = segt[2*node] + segt[2*node+1];
		node >>= 1;
	}
}

int query(int deb, int fin){
	deb += N;
	fin += N;
	int ans = 0;
	while (deb <= fin){
		if (deb&1){
			ans += segt[deb];
			deb++;
		}
		if (fin%2 == 0){
			ans += segt[fin];
			fin--;
		}
		deb >>= 1;
		fin >>= 1;
	}
	return ans;
}

int lca(int a, int b){
	if (depth[a] < depth[b]) swap(a,b);
	int delta = depth[a]-depth[b];
	for (int i=19; i>=0; --i){
		if (delta&(1<<i)){
			a = pere[i][a];
		}
	}
	if (a == b) return a;
	for (int i=19; i>=0; --i){
		if (pere[i][a] != pere[i][b]){
			a = pere[i][a];
			b = pere[i][b];
		}
	}
	return pere[0][a];
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m,k;
	cin >> n >> m >> k;
	for (int i=1; i<n; ++i){
		int a,b;
		cin >> a >> b;
		a--; b--;
		id[a+b*1e6] = i;
		id[b+a*1e6] = i;
		adj[a].emplace_back(b);
		adj[b].emplace_back(a);
	}
	dfs();
	for (int i=1; i<20; ++i){
		for (int j=0; j<n; ++j){
			pere[i][j] = pere[i-1][pere[i-1][j]];
		}
	}
	for (int i=0; i<m; ++i){
		int nb;
		cin >> nb;
		vector<int> crt_ins;
		for (int j=0; j<nb; ++j){
			int a;
			cin >> a;
			a--;
			crt_ins.emplace_back(a);
		}
		sort(crt_ins.begin(),crt_ins.end(),[](int a, int b){return in[a] < in[b];});
		crt_ins.emplace_back(crt_ins[0]);
		for (int j=1; j<crt_ins.size(); ++j){
			modify(in[crt_ins[j-1]],1);
			modify(in[crt_ins[j]],1);
			modify(in[lca(crt_ins[j],crt_ins[j-1])],-2);
		}
	}
	vector<int> res;
	for (int i=1; i<n; ++i){
		if (query(in[i],out[i]-1) >= 2*k){
			res.emplace_back(id[i+1e6*pere[0][i]]);
		}
	}
	cout << res.size() << '\n';
	sort(res.begin(),res.end());
	for (int i:res) cout << i << ' ';
	return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int32_t main()':
railway.cpp:107:18: 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]
  107 |   for (int j=1; j<crt_ins.size(); ++j){
      |                 ~^~~~~~~~~~~~~~~

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