Submission #454927

#	Time	Username	Problem	Language	Result	Execution time	Memory
454927		naman1601	Railway (BOI17_railway)	C++17	100 / 100	684 ms	49496 KiB

railway

/*
++[---------->+<]>.-[------>+<]>-.++++++++.+++++.-[->+++++<]>-.-[--->++<]>--.+.[--->+<]>---.[->+++<]>++.++++++.-------.++++++.--[--->+<]>.-[->+++<]>-..+++++++++++++.[----->++<]>.------------.+[----->+<]>.--------.+++++++++++++.-------------.--[--->+<]>-.---[->++++<]>-.++++[->+++<]>.--[--->+<]>-.[->+++<]>++.-.+++.---.-[->+++<]>.-[--->++<]>+.++++.------.[--->+<]>---.+[----->+<]>.------------.+++++++.-------.--[--->+<]>---.+++[->+++<]>++..+++++++++.---------.-[->+++<]>.+[----->+<]>+.-------------.+++++++.+.----[->+++<]>-.
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long big;
typedef long double ludo;
#define pbb pair<big, big>
#define pii pair<int, int>
#define fe first
#define se second
#define maxheap priority_queue
#define mset multiset
#define uset unordered_set
#define umap unordered_map
#define fr(i, s, e) for(int i = s; i < e; i++)
#define revfr(i, s, e) for(int i = s - 1; i >= e; i--)
#define getv(v, n) for(int i = 0; i < n; i++) cin >> v[i];
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL)
#define nl "\n"
// #define debug(text) if(do_debug) {cout << (#text) << ": " << text << endl;}
#ifdef naman1601
#define debug(text) cout << (#text) << ": " << text << endl;
#else
#define debug(text)
#endif

const big mod = 1000000007;
// const big mod = 998244353;
const big infinity = 1000000000000000000;
const int inf = 1e9 + 5;
bool do_debug = false;


const int maxn = 1e5 + 5;
int n_nodes, n_edges;
vector<int> adj[maxn];
map<int, int> edge_id[maxn];
vector<int> ans;
int entry[maxn];
int emapper[maxn];
int tim;
// vector<int> rev[maxn];
// vector<int> path;

bool by_entry(int u, int v) {

	if(entry[u] < entry[v]) {

		return true;

	} else {

		return false;
	}
}


struct lca {

	int n, tl;
	vector<int> t;
	vector<int> first;
	vector<int> euler;
	vector<int> dv;

	void init(int N) {

		n = N;
		euler.clear();
		euler.reserve(2 * n);
		first.clear();
		first.resize(n);
		dv.clear();
		dv.resize(n);

		dv[0] = 0;
		dfs(0, 0);

		tl = euler.size();
		t.clear();
		t.resize(tl << 2, -1);
		build(1, 0, tl - 1);
	}

	int get_lca(int u, int v) {

		int l = first[u], r = first[v];
		if(l > r) swap(l, r);
		return query(1, 0, tl - 1, l, r);
	}

	void dfs(int node, int parent) {

		first[node] = euler.size();
		euler.push_back(node);

		for(int next : adj[node]) {

			if(next == parent) continue;

			dv[next] = dv[node] + 1;
			dfs(next, node);
			euler.push_back(node);
		}
	}

	int task(int child1, int child2) {

		if(child1 == -1) return child2;
		if(child2 == -1) return child1;

		if(dv[child1] < dv[child2]) {

			return child1;

		} else {

			return child2;
		}
	}

	void build(int node, int l, int r) {
	
		if(l == r) {
	
			t[node] = euler[l];
	
		} else {
	
			int mid = (l + r) >> 1;
			build(node << 1, l, mid);
			build((node << 1) + 1, mid + 1, r);
			t[node] = task(t[node << 1], t[(node << 1) + 1]);
		}
	}

	int query(int node, int l, int r, int lq, int rq) {
	
		if(lq > rq) {
	
			return -1;
	
		} else if(lq <= l && rq >= r) {
	
			return t[node];
	
		} else {
	
			int mid = (l + r) >> 1;
			return task(query(node << 1, l, mid, lq, min(rq, mid)), query((node << 1) + 1, mid + 1, r, max(lq, mid + 1), rq));
		}
	}
};


lca lca;


struct hld_t {

	// this fenwick tree supports only range updates and point queries
	// can also be modified to support point updates and range queries
	// but not both simultaneously

	int tl;
	vector<int> t;

	void init(int len, int val) {

		tl = len;
		t = vector<int>(tl, val);
	}

	void update(int index, int val) {

		for(; index < tl; index = index | (index + 1)) {

			t[index] += val;
		}
	}

	void range_update(int l, int r, int val) {

		update(l, val);
		update(r + 1, -val);
	}

	int point_query(int index) {

		int rv = 0;

		for(; index >= 0; index = (index & (index + 1)) - 1) {

			rv += t[index];
		}

		return rv;
	}

	void point_update(int index, int val) {

		update(index, val);
	}

	int range_query(int l, int r) {

		return point_query(r) - point_query(l - 1);
	}
};


struct hld {

	int n;
	vector<int> hld_path;
	vector<int> pos;
	vector<int> heavy_of;
	vector<int> head_of;
	vector<int> parent_of;

	hld_t t;

	hld(int N) {

		n = N;

		hld_path.clear();
		hld_path.reserve(n);
		pos.clear();
		pos.resize(n);
		heavy_of.clear();
		heavy_of.resize(n, -1);
		head_of.clear();
		head_of.resize(n);
		parent_of.clear();
		parent_of.resize(n);

		t.init(n, 0);

		parent_of[0] = 0;
		dfs(0);
		head_of[0] = 0;
		decompose(0);

		// t.build(hld_path);
	}

	int dfs(int node) {

		int subtree_size = 1;
		int current_heavy_size = -1;

		for(int next : adj[node]) {

			if(next == parent_of[node]) continue;

			parent_of[next] = node;
			int next_size = dfs(next);
			subtree_size += next_size;

			if(next_size > current_heavy_size) {

				current_heavy_size = next_size;
				heavy_of[node] = next;
			}
		}

		return subtree_size;
	}

	void decompose(int node) {

		pos[node] = hld_path.size();
		hld_path.push_back(node);

		if(heavy_of[node] != -1) {

			head_of[heavy_of[node]] = head_of[node];
			decompose(heavy_of[node]);
		}

		for(int next : adj[node]) {

			if(next == heavy_of[node] || next == parent_of[node]) continue;

			head_of[next] = next;
			decompose(next);
		}
	}

	// int task(int v1, int v2) {

	// 	return v1 + v2;
	// }

	// int query(int node, int ancestor) {

	// 	int retval = 0;

	// 	for(; head_of[node] != head_of[ancestor]; node = parent_of[head_of[node]]) {

	// 		retval = task(retval, t.query(pos[head_of[node]], pos[node]));
	// 	}

	// 	retval = task(retval, t.query(pos[ancestor], pos[node]));
	// 	return retval;
	// }

	int query(int v) {

		return t.point_query(pos[v]);
	}

	void update(int node, int ancestor) {

		for(; head_of[node] != head_of[ancestor]; node = parent_of[head_of[node]]) {

			t.range_update(pos[head_of[node]], pos[node], 1);
		}

		t.range_update(pos[ancestor] + 1, pos[node], 1);
	}

	// void update(int node, int value) {

	// 	t.update(pos[node], value);
	// }
};

void dfs(int v, int p) {

	entry[v] = tim++;

	for(int u : adj[v]) {

		if(u == p) continue;
		emapper[u] = edge_id[u][v];
		dfs(u, v);
	}
}


void solve() {

	int n_people, quorum;
	cin >> n_nodes >> n_people >> quorum;
	quorum *= 2;

	fr(i, 0, n_nodes) emapper[i] = -1;

	fr(i, 0, n_nodes - 1) {

		int u, v;
		cin >> u >> v;
		u--; v--;

		adj[u].push_back(v);
		adj[v].push_back(u);
		edge_id[u][v] = i;
		edge_id[v][u] = i;
	}

	tim = 0;
	dfs(0, 0);
	lca.init(n_nodes);
	hld h(n_nodes);

	fr(i, 0, n_people) {

		int sz;
		cin >> sz;

		vector<int> vl(sz);

		fr(j, 0, sz) {

			cin >> vl[j];
			vl[j]--;
		}

		sort(vl.begin(), vl.end(), by_entry);
		vl.push_back(vl[0]);

		fr(j, 0, sz) {

			int LCA = lca.get_lca(vl[j], vl[j + 1]);
			if(vl[j] != LCA)
			h.update(vl[j], LCA);
			if(vl[j + 1] != LCA)
			h.update(vl[j + 1], LCA);
		}
	}

	fr(i, 0, n_nodes) {

		if(emapper[i] == -1) continue;

		int rv = h.query(i);

		if(rv >= quorum) {

			ans.push_back(emapper[i]);
		}
	}

	cout << (int)ans.size() << nl;
	sort(ans.begin(), ans.end());

	for(int e : ans) {

		cout << e + 1 << " ";
	}

	cout << nl;
}


int main() {
	
	speed;

	int q = 1;
	// cin >> q;

	while(q-- > 0) {

		solve();
	}

	return 0;
}

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