Submission #515578

#	Time	Username	Problem	Language	Result	Execution time	Memory
515578		akhan42	Railway (BOI17_railway)	C++17	100 / 100	365 ms	39384 KiB

railway

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define mp make_pair

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
//typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }


const int MX = 100 * 1000 + 10;
const int mxpw = 20;
vii tobe_cleaned;

struct Seg {
	int n;
	vi t;

	Seg(int n): n(n) {
		t.assign(2 * n, 0);
	}

	void update(int l, int r, bool clean = false, int val = 1) {
		if(clean)
			tobe_cleaned.eb(l, r);
		for(l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
			if(l & 1) t[l++] += val;
			if(r & 1) t[--r] += val;
		}
	}

	int query(int p) {
		int res = 0;
		for(p += n; p > 0; p >>= 1)
			res += t[p];
		return res;
	}
};

vi gr[MX];
int timer = 0;
int tin[MX], tout[MX];
int par[mxpw][MX];
int sub_sz[MX];
int depth[MX];
int root[MX];
int node2edge[MX];
map<ii, int> edges;


void dfs1(int node = 1, int pr = 0, int dep = 0) {
	depth[node] = dep;
	par[0][node] = pr;
	sub_sz[node] = 1;
	if(pr != 0)
		node2edge[node] = edges[mp(min(node, pr), max(node, pr))];

	for(int &nb: gr[node]) {
		gr[nb].erase(find(all(gr[nb]), node));

		dfs1(nb, node, dep + 1);
		sub_sz[node] += sub_sz[nb];
		if(sub_sz[nb] > sub_sz[gr[node][0]])
			swap(nb, gr[node][0]);
	}
}

void dfs2(int node = 1) {
	tin[node] = ++timer;
	for(int nb: gr[node]) {
		root[nb] = (gr[node][0] == nb ? root[node] : nb);
		dfs2(nb);
	}
	tout[node] = timer;
}

Seg* seg_gl;
Seg* seg_cur;

void process_path(int u, int v, bool upd_gl = true) {
	for(; root[u] != root[v]; v = par[0][root[v]]) {
		if(depth[root[u]] > depth[root[v]])
			swap(u, v);
		seg_cur->update(tin[root[v]], tin[v], true);
		if(upd_gl) seg_gl->update(tin[root[v]], tin[v]);
	}
	if(depth[u] > depth[v]) swap(u, v);
	seg_cur->update(tin[u], tin[v], true);
	if(upd_gl) seg_gl->update(tin[u], tin[v]);
}

void clean() {
	for(ii lr: tobe_cleaned) {
		int l = lr.F, r = lr.S;
		seg_cur->update(l, r, false, -1);
	}
	tobe_cleaned.clear();
}

int lca_node(int u, int v) {
	for(; root[u] != root[v]; v = par[0][root[v]])
		if(depth[root[u]] > depth[root[v]])
			swap(u, v);
	return depth[u] > depth[v] ? v : u;
}


void solve() {
//	tout[0] = MX;
	int n, m, k;
	cin >> n >> m >> k;
	forbn(i, 1, n) {
		int a, b;
		cin >> a >> b;
		gr[a].pb(b);
		gr[b].pb(a);
		edges[mp(min(a, b), max(a, b))] = i;
	}

	seg_gl = new Seg(n + 1);
	seg_cur = new Seg(n + 1);
	dfs1();
//	root[1] = 1;
	dfs2();

	forbn(d, 1, mxpw) {
		forn(i, n + 1) {
			int to = par[d - 1][i];
			par[d][i] = par[d - 1][to];
		}
	}

	forn(i, m) {
		int s;
		cin >> s;
		vi nodes(s);
		int lca = -1;
		forn(j, s) {
			cin >> nodes[j];
			if(j == 0)
				lca = nodes[j];
			else
				lca = lca_node(lca, nodes[j]);
		}
		process_path(0, lca, false);
		forn(j, s) {
			int u = nodes[j];
			if(seg_cur->query(tin[u]))
				continue;
			for(int pw = mxpw - 1; pw >= 0; pw--)
				if(seg_cur->query(tin[par[pw][u]]) == 0)
					u = par[pw][u];

			process_path(nodes[j], u);
		}
		clean();
	}

	vi ans;
	forbn(u, 2, n + 1) {
//		cerr << u << ' ' << seg_gl->query(tin[u]) << '\n';
		if(seg_gl->query(tin[u]) >= k) {
			ans.pb(node2edge[u]);
		}
	}
	cout << sz(ans) << '\n';
	sort(all(ans));
	for(int a: ans) {
		cout << a << ' ';
	}
}


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

//	freopen("grassplant.in", "r", stdin);
//	freopen("grassplant.out", "w", stdout);

	int t = 1;
//	cin >> t;
	while(t--) {
		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