Submission #864553

#	Time	Username	Problem	Language	Result	Execution time	Memory
864553		maks007	Railway (BOI17_railway)	C++14	0 / 100	1056 ms	46640 KiB

railway

// Bismi Allah
#include "bits/stdc++.h"

using namespace std;

int T, K;

vector <vector <int>> g;
map <pair <int,int>,int> pos;
map <int,pair <int,int>> revPos;
vector <int> rk, depth, head, heavy, t, parent;

void push(int v, int vl, int vr) {
	if(vl != vr) {
		t[2*v+1] += t[v];
		t[2*v+2] += t[v];
		t[v] = 0;
 	}
}

int get(const int pos, int vl = 0, int vr = K - 1, int v = 0) {
	push(v, vl, vr);
	if(vl == vr) return t[v];
	int vm = (vl + vr) / 2;
	if(pos <= vm) return get(pos, vl, vm, 2*v+1);
	else return get(pos, vm+1, vr, 2*v+2);
}

void update(const int l, const int r, int vl = 0, int vr = K - 1, int v = 0) {
	push(v, vl, vr);
	if(r < vl || l > vr) return;
	if(l <= vl && vr <= r) {
		t[v] += 1;
		push(v, vl, vr);
		return;
	}
	int vm = (vl + vr) / 2;
	update(l, r, vl, vm, 2*v+1);
	update(l, r, vm+1, vr, 2*v+2);
}

void distance(int a, int b) {
	while(head[a] != head[b]) {	
		if(depth[head[a]] > depth[head[b]]) swap(a, b);
		update(pos[{min(b, parent[b]), max(b, parent[b])}], pos[{min(a, heavy[a]), max(a, heavy[a])}]);
		b = parent[head[b]];
	}
	if(a == b) {
		return;
	}
	if(depth[a] > depth[b]) swap(a, b);
	update(pos[{min(b, parent[b]), max(b, parent[b])}], pos[{min(a, heavy[a]), max(a, heavy[a])}]);
}

void compose(int v = 0, int h = 0, int p = -1) {
	//cout << heavy[v] << "\n";
	head[v] = h;
	pos[{min(v, p), max(v, p)}] = T ++;
	revPos[T-1] = {min(v, p), max(v, p)};
	if(heavy[v] != -1) {
		compose(heavy[v], h, v);
	}
	for(auto u : g[v]) {
		if(p == u || u == heavy[v]) continue;
		compose(u, u, v);
	}
}

void dfs(int v = 0, int p = -1) {
	parent[v] = p;
	rk[v] = 1;
	if(p == -1) depth[v] = 0;
	else depth[v] = depth[p] + 1;
	for(auto u : g[v]) {
		if(u == p) continue;
		dfs(u, v);
		rk[v] += rk[u];
	}
	if(rk[v] == 1) return;
	for(auto u : g[v]) {
		if(u == p) continue;
		if(rk[heavy[v]] < rk[u] || heavy[v] == -1) {
			heavy[v] = u;
		}
	} 
}

signed main () {
	int n, m, k;
	cin >> n >> m >> k;
	T = 0;
	K = 1;
	while(K < n) K <<= 1;
	t.resize(2*K-1);
	rk.resize(n);
	depth.resize(n);
	head.resize(n);
	g.resize(n);
	heavy.resize(n, -1);
	parent.resize(n);
	map <pair <int,int>,int> edge;
	for(int i = 0, u, v; i < n - 1; i ++) {
		cin >> u >> v;
		u --, v --;
		edge[{u, v}] = i;
		edge[{v, u}] = i;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs();
	compose();
	for(int i = 0; i < m; i ++) {
		int sz;
		cin >> sz;
		int a, b;
		cin >> a >> b;
		distance(a, b);
	}
	vector <int> ans;
	for(int i = 0; i < n; i ++) {
		if(get(i) >= k)
		ans.push_back(edge[revPos[i]] + 1);
		
	}
	cout << ans.size() << "\n";
	for(auto i : ans) cout << i << " "; 

	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