Submission #169950

#	Time	Username	Problem	Language	Result	Execution time	Memory
169950		moonrabbit2	Railway (BOI17_railway)	C++17	100 / 100	322 ms	24048 KiB

railway

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int> tii;
typedef tuple<ll,ll,ll> tll;
typedef vector<vector<ll>> mat;
const ll mod=1e9+7;
const int N=1e5+5;
int n,q,k;
int in[N],out[N],rev[N],cur,h[N],p[18][N],ep[N],s[N];
int tree[4*N];
vector<pii> g[N];
vector<int> ans;
void upd(int nd,int l,int r,int x,int v){
	if(l==r){
		tree[nd]=v;
		return;
	}
	int m=(l+r)>>1;
	if(x<=m) upd(nd<<1,l,m,x,v);
	else upd(nd<<1|1,m+1,r,x,v);
	tree[nd]=min(tree[nd<<1],tree[nd<<1|1]);
}
int qry(int nd,int l,int r,int s,int e){
	if(r<s||e<l) return 1e9;
	if(s<=l&&r<=e) return tree[nd];
	int m=(l+r)>>1;
	return min(qry(nd<<1,l,m,s,e),qry(nd<<1|1,m+1,r,s,e));
}
void dfs(int u){
	in[u]=++cur; rev[in[u]]=u;
	for(auto &it : g[u]) if(it.fi!=p[0][u]){
		p[0][it.fi]=u;
		ep[it.fi]=it.se;
		h[it.fi]=h[u]+1;
		dfs(it.fi);
	}
	out[u]=cur;
}
int lca(int u,int v){
	if(h[u]>h[v]) swap(u,v);
	int d=h[v]-h[u];
	for(int bit=17;bit>=0;bit--) if(d&(1<<bit)) v=p[bit][v];
	if(u==v) return u;
	for(int bit=17;bit>=0;bit--) if(p[bit][u]!=p[bit][v]){
		u=p[bit][u]; v=p[bit][v];
	}
	return p[0][u];
}
void dfs2(int u){
	upd(1,1,n,in[u],1e9);
	while(qry(1,1,n,in[u],out[u])!=1e9){
		int v=rev[qry(1,1,n,in[u],out[u])];
		s[v]++; s[u]--;
		dfs2(v);
	}
}
void dfs3(int u){
	for(auto &it : g[u]) if(it.fi!=p[0][u]){
		dfs3(it.fi);
		s[u]+=s[it.fi];
	}
	if(s[u]>=k) ans.emplace_back(ep[u]);
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>q>>k;
	for(int u,v,i=1;i<n;i++){
		cin>>u>>v;
		g[u].emplace_back(v,i);
		g[v].emplace_back(u,i);
	}
	dfs(1);
	for(int bit=1;bit<18;bit++) for(int i=1;i<=n;i++) p[bit][i]=p[bit-1][p[bit-1][i]];
	for(int i=1;i<=n;i++) upd(1,1,n,i,1e9);
	for(int s,i=1;i<=q;i++){
		vector<int> vec;
		cin>>s;
		int u=-1;
		for(int v,j=1;j<=s;j++){
			cin>>v;
			vec.emplace_back(in[v]);
			if(u==-1) u=v;
			u=lca(u,v);
		}
		sort(vec.begin(),vec.end());
		for(auto &it : vec) upd(1,1,n,it,it);
		for(int j=1;j<vec.size();j++){
			int uv=lca(rev[vec[j-1]],rev[vec[j]]);
			upd(1,1,n,in[uv],in[uv]);
		}
		dfs2(u);
	}
	dfs3(1);
	sort(ans.begin(),ans.end());
	cout<<ans.size()<<"\n";
	for(auto &it : ans) cout<<it<<" ";
    return 0;
}

Compilation message (stderr)

railway.cpp: In function 'int main()':
railway.cpp:94:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=1;j<vec.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