Submission #955655

#	Time	Username	Problem	Language	Result	Execution time	Memory
955655		Alexabcde1	Railway (BOI17_railway)	C++14	100 / 100	226 ms	70604 KiB

railway

#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
long long n,m,k,aa,bb,cnt,ind[100005],t,timer,in[100005],out[100005],par[100005][50],psum[100005],vis[100005],vis2[100005];
vector<pair<long long,long long> > ve;
vector<long long> adj[100005];
map<pair<long long,long long>,long long> mp;
vector<long long> ans;
void dfs(long long x,long long pre){
	vis[x]=1;
	in[x]=timer; timer++;
	par[x][0]=pre;
	for (int i=1;i<=40;i++) par[x][i]=par[par[x][i-1]][i-1];
	cnt++;
	ind[x]=cnt;
	for (int ii=0;ii<adj[x].size();ii++){
		if (!vis[adj[x][ii]]) dfs(adj[x][ii],x);
	}
	out[x]=timer; timer++;
	return;
}
bool an(long long u,long long v){
	return in[u]<=in[v] && out[u]>=out[v];
}
long long lca(long long u,long long v){
	if (an(u,v)) return u;
	if (an(v,u)) return v;
	for (int i=39;i>=0;--i){
		if (!an(par[u][i],v)) u=par[u][i];
	}
	return par[u][0];
}
void dfs2(long long x,long long pre){
	vis2[x]=1;
	for (int i=0;i<adj[x].size();i++){
		if (vis2[adj[x][i]]) continue;
		dfs2(adj[x][i],x);
		psum[x]+=psum[adj[x][i]];
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>m>>k;
	for (int i=1;i<n;i++){
		cin>>aa>>bb;
		mp[{aa,bb}]=i;
		mp[{bb,aa}]=i;
		adj[aa].push_back(bb);
		adj[bb].push_back(aa);
	}
	dfs(1,1);
	while (m--){
		cin>>t;
		ve.clear();
		for (int i=0;i<t;i++){
			long long tmp;
			cin>>tmp;
			ve.push_back({ind[tmp],tmp});
		}
		sort(ve.begin(),ve.end());
		for (int i=0;i<t;i++){
			long long u=ve[i].s;
			long long v=ve[(i+1)%ve.size()].s;
			long long lc=lca(u,v);
			psum[u]++; psum[v]++; psum[lc]-=2;
		}
	}
	dfs2(1,1);
	for (int i=1;i<=n;i++) {
		//cout<<psum[i]<<endl;
		if (psum[i]>=2*k){
			ans.push_back(mp[{i,par[i][0]}]);
		}
	}
	sort(ans.begin(),ans.end());
	cout<<ans.size()<<endl;
	for (int i=0;i<ans.size();i++){
		if (i==0) cout<<ans[i];
		else cout<<" "<<ans[i];
	}
	cout<<endl;
}

Compilation message (stderr)

railway.cpp: In function 'void dfs(long long int, long long int)':
railway.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for (int ii=0;ii<adj[x].size();ii++){
      |                ~~^~~~~~~~~~~~~~
railway.cpp: In function 'void dfs2(long long int, long long int)':
railway.cpp:36:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for (int i=0;i<adj[x].size();i++){
      |               ~^~~~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:79:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for (int i=0;i<ans.size();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