Submission #291078

#	Time	Username	Problem	Language	Result	Execution time	Memory
291078		Blagojce	Railway (BOI17_railway)	C++11	100 / 100	195 ms	34800 KiB

railway

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const ll inf = 1e18;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;

mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 2e5;


vector<pii> g[mxn];
int sparse[mxn][20];
int depth[mxn];
int pos[mxn];
int sz[mxn];
int par[mxn];

int tmp = 0;
void dfs0(int u, int p){
	pos[u] = tmp ++;
	sparse[u][0] = p;
	fr(i, 1, 20) sparse[u][i] = sparse[sparse[u][i-1]][i-1];
	sz[u] = 1;
	for(auto e : g[u]){
		if(e.st == p) continue;
		depth[e.st] = depth[u] + 1;
		par[e.st] = e.nd;
		dfs0(e.st, u);
		sz[u] += sz[e.st];
	}
}
int lca(int a, int b){
	int d = min(depth[a], depth[b]);
	for(int i = 19; i >= 0; i --){
		if(depth[a]-(1<<i) >= d) a = sparse[a][i];
		if(depth[b]-(1<<i) >= d) b = sparse[b][i];
	}
	if(a == b) return a;
	for(int i = 19; i >= 0; i --){
		if(sparse[a][i] != sparse[b][i]){
			a = sparse[a][i];
			b = sparse[b][i];
		}
	}
	return sparse[a][0];
}
int memo[mxn][20];

void update(int u, int p){
	for(int i = 19; i >= 0; i --){
		if(depth[u]-(1<<i) >= depth[p]){
			memo[u][i] += 1;
			u = sparse[u][i];
		}
	}
}
int n, m, k;
void restore(){
	for(int i = 19; i >= 1; i --){
		fr(u, 0, n){
			memo[u][i-1] += memo[u][i];
			memo[sparse[u][i-1]][i-1] += memo[u][i];
		}
	}
}

void solve(){
	cin >> n >> m >> k;
	fr(i, 0, n-1){
		int u, v;
		cin >> u >> v;
		--u, --v;
		g[u].pb({v, i+1});
		g[v].pb({u, i+1});
	}
	dfs0(0, 0);
	fr(q, 0, m){
		int s;
		cin >> s;
		int a[s];
		fr(i, 0, s){
			cin >> a[i]; 
			-- a[i];
		}
		sort(a, a + s, [](const int &i, const int &j){
			return pos[i] < pos[j];
		});
		vector<int> v;
		fr(i, 0, s) v.pb(a[i]);
		fr(i, 0, s-1){
			v.pb(lca(a[i], a[i+1]));
		}
		bool root = false;
		sort(all(v));
		if(v[0] == 0) root = true;
		
		v.erase(unique(all(v)), v.end());
		
		sort(all(v), [](const int &i, const int &j){
			return pos[i] < pos[j];
		});
		stack<int> S;
		S.push(0);
		for(auto u : v){
			if(u == 0) continue;
			while(pos[S.top()]+sz[S.top()] <= pos[u]) S.pop();
			
			if(S.top() != 0 || root) update(u, S.top());
			
			S.push(u);
		}
	}
	restore();
	vector<int> sol;
	fr(i, 1, n){
		if(memo[i][0] >= k){
			sol.pb(par[i]);
		}
	}
	sort(all(sol));
	cout<<sol.size()<<endl;
	for(auto u : sol) cout<<u<<' ';
	cout<<endl;
	
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
}

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