Submission #758104

#	Time	Username	Problem	Language	Result	Execution time	Memory
758104		MetalPower	Railway (BOI17_railway)	C++14	100 / 100	303 ms	32552 KiB

railway

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

#define pii pair<int, int>
#define fi first
#define se second

const int MX = 2e5 + 10;
const int LG = 19;

struct segtree{
	int st[MX << 1];

	void upd(int l, int r, int v){
		for(l += MX, r += MX + 1; l < r; l >>= 1, r >>= 1){
			if(l & 1) st[l++] += v;
			if(r & 1) st[--r] += v;
		}
	}

	int que(int p){
		int res = 0;
		for(p += MX; p > 0; p >>= 1) res += st[p];
		return res;
	}
} S;

struct segversion{
	int st[MX << 1];

	void upd(int l, int r, int v){
		for(l += MX, r += MX + 1; l < r; l >>= 1, r >>= 1){
			if(l & 1) st[l++] = v;
			if(r & 1) st[--r] = v;
		}
	}

	int que(int p){
		int res = 0;
		for(p += MX; p > 0; p >>= 1) res = max(res, st[p]);
		return res;
	}
} T;

vector<int> adj[MX];
int N, M, K, par[MX], head[MX], sp[MX][LG];
int sz[MX], dep[MX], in[MX], out[MX], tim = 0;

void dfs(int u, int v){
	if(v != 0) adj[u].erase(find(adj[u].begin(), adj[u].end(), v));

	sz[u] = 1; dep[u] = dep[v] + 1;
	sp[u][0] = par[u] = v;
	for(int i = 1; i < LG; i++) sp[u][i] = sp[sp[u][i - 1]][i - 1];

	for(int& nxt : adj[u]){
		dfs(nxt, u);
		sz[u] += sz[nxt];
		if(sz[nxt] > sz[adj[u][0]]) swap(nxt, adj[u][0]);
	}
}

void dfs2(int u){
	in[u] = ++tim;
	for(int nxt : adj[u]){
		if(nxt == adj[u][0]) head[nxt] = head[u];
		else head[nxt] = nxt;
		dfs2(nxt);
	}
	out[u] = tim;
}

void init(){
	dfs(1, 0);
	head[1] = 1;
	dfs2(1);
}

int lca(int u, int v){
	if(dep[u] > dep[v]) swap(u, v);

	int df = dep[v] - dep[u];
	for(int j = 0; j < LG; j++){
		if(df >> j & 1) v = sp[v][j];
	}

	if(u == v) return u;

	for(int j = LG - 1; j >= 0; j--){
		if(sp[u][j] != sp[v][j]){
			u = sp[u][j];
			v = sp[v][j];
		}
	}

	return sp[u][0];
}

void upd(int u, int v, int val){
	for(; head[u] != head[v]; v = par[head[v]]){
		if(dep[u] > dep[v]) swap(u, v);
		S.upd(in[head[v]], in[v], 1);
		T.upd(in[head[v]], in[v], val);
	}
	if(dep[u] > dep[v]) swap(u, v);
	S.upd(in[u], in[v], 1);
	T.upd(in[u], in[v], val);
}

vector<pair<pii, int>> edges;

int find_rep(int u, int root, int ver){ // find ancestor of u that is lower than root and off
	for(int i = LG - 1; i >= 0; i--){
		if(dep[sp[u][i]] > dep[root] && T.que(in[sp[u][i]]) != ver) u = sp[u][i];
	}
	return u;
}

int idx_edge[MX];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> M >> K;
	for(int i = 1; i < N; i++){
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
		edges.push_back({{u, v}, i});
	}

	init();
	for(auto edge : edges){
		if(dep[edge.fi.fi] > dep[edge.fi.se]) idx_edge[edge.fi.fi] = edge.se;
		else if(dep[edge.fi.fi] < dep[edge.fi.se]) idx_edge[edge.fi.se] = edge.se;
	}

	for(int i = 1; i <= M; i++){

		int s; cin >> s;
		vector<int> curr;

		int root = -1;
		for(int j = 1; j <= s; j++){
			int nd; cin >> nd;
			if(root == -1) root = nd;
			else root = lca(root, nd);
			curr.push_back(nd);
		}

		T.upd(in[root], in[root], i);
		for(int x : curr){
			if(x == root || T.que(in[x]) == i) continue;
			int nd = find_rep(x, root, i);
			upd(x, nd, i);
		}
	}

	vector<int> answ;

	for(int i = 1; i <= N; i++){
		if(S.que(in[i]) >= K) answ.push_back(idx_edge[i]);
	}

	sort(answ.begin(), answ.end());

	cout << answ.size() << '\n';
	for(int x : answ) cout << x << " ";
	cout << '\n';
}

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