Submission #487661

#	Time	Username	Problem	Language	Result	Execution time	Memory
487661		codr0	Railway (BOI17_railway)	C++14	0 / 100	1089 ms	87088 KiB

railway

// Code by Parsa Eslami
     
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
//#define int long long
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define MOD(x) while(x>=M) x-=M; while(x<0) x+=M;
#define all(x) x.begin(),x.end()
#define debug(x) cerr<<#x<<" : "<<x<<'\n'
 
using namespace std;
typedef pair<int,int> pii;
const int N=1e5+3;
const int M=5e4+100;
bitset<M/8+100> bt[N];
vector<int> adj[N];
int par[N][20],h[N];
int ans[N];
int dp[N];
    
    bool bit(int i,int j){ return ((j>>i)&1); }
    
    void FILL(){
    	FOR(lg,1,19)
    		FOR(i,1,N-1)	par[i][lg]=par[par[i][lg-1]][lg-1];
	}
	
	int MV(int u,int K){
		FOR(i,0,19) if(bit(i,K)) u=par[u][i];
		return u;
	}
	
	int LCA(int u,int v){
		if(h[u]<h[v]) swap(u,v);
		u=MV(u,h[u]-h[v]);
		if(u==v) return u;
		FORR(i,19,0){
			if(par[u][i]!=par[v][i]){
				u=par[u][i];
				v=par[v][i];
			}
		}
		return (par[v][0]);
	}
    
    void dfs(int v,int p){
    	par[v][0]=p;
    	h[v]=h[p]+1;
    	for(int u:adj[v])
    		if(u!=p){
    			dfs(u,v);
			}
	}
    
    void DFS(int v,int p){
    	for(int u:adj[v]){
    		if(u!=p){
    			DFS(u,v);
    			bt[v]|=bt[u];
    			dp[v]+=dp[u];
			}
		}
		ans[v]+=((bt[v]).count()+dp[v]);
	}
    
	int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	int n,m,k;
	cin>>n>>m>>k;
	vector<pii> E;
	FOR(i,1,n-1){
		int u,v; cin>>u>>v;
		adj[u].pb(v); adj[v].pb(u);
		E.pb({u,v});
	}
	dfs(1,0);
	FILL();
	FOR(i,1,n) FOR(j,1,M/8) bt[i][j]=0;
	FOR(i,1,m){
		int si; cin>>si;
		int u; cin>>u; int lc=u; bt[u][((i%(M/8-1))+1)]=1;
		FOR(i,1,si-1){
			cin>>u; lc=LCA(lc,u); bt[u][((i%(M/8-1))+1)]=1;
		}
		dp[lc]--;
		if(i%(M/8-1)==0){
			//clear
			DFS(1,0);
			FOR(i,1,n){
				dp[i]=0;
			}
			FOR(i,1,n) FOR(j,1,M/8+2) bt[i][j]=0;
		}
	}
	DFS(1,0);
	vector<int> ot; ot.clear();
	FOR(i,0,SZ(E)-1){
		int u=E[i].F;
		int v=E[i].S;
		if(par[v][0]==u) swap(u,v);
		if(ans[u]>=k) ot.pb(i+1);
	}
	cout<<SZ(ot)<<'\n';
	for(int o:ot) cout<<o<<" ";
	
	return 0;
	}

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