Submission #463808

#	Time	Username	Problem	Language	Result	Execution time	Memory
463808		xyzyzl	Railway (BOI17_railway)	C++14	100 / 100	286 ms	23736 KiB

railway

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100005;
#define bitinc(x) x&-x

int n, m, k;
vector<int> adj[MAXN];
int par[100005][20];
int tmp = 0, in[200005], ot[200005], bit[200005];

int sum(int ind)
{
	int sm = 0;
	while(ind > 0)
	{
		sm += bit[ind];
		ind -= bitinc(ind);
	}
	return sm;
}
void upd(int ind, int val)
{
	while(ind <= n)
	{
		bit[ind] += val;
		ind += bitinc(ind);
	}
}

vector<pair<int, int> > eg;

void dfs(int v, int p)
{
	in[v] = ++tmp;
	par[v][0] = p;
	for(int i = 1; i < 20; i++)
		par[v][i] = par[par[v][i-1]][i-1];
	for(int x : adj[v])
	{
		if(x == p) continue;
		dfs(x,v);
	}
	ot[v] = tmp;
}

bool anc(int u, int v)
{
	return (in[u] <= in[v] && ot[u] >= ot[v]);
}

// method finding all lca's
int lca(int u, int v)
{
	if(anc(u,v))
		return u;
	for(int i = 19; i >= 0; i--)
	{
		// as a verifier make sure par[u][i] >= 0 s.t. no array out of bounds
		if(par[u][i] >= 0 && !anc(par[u][i], v))
			u = par[u][i];
	}
	return par[u][0];
}

bool comp(int a, int b)
{
	return in[a] < in[b];
}

int main()
{
	cin >> n >> m >> k;
	for(int i = 1; i < n; i++)
	{
		int u, v; cin >> u >> v;
		--u; --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
		eg.push_back({u,v});
	}
	dfs(0, 0);
	for(int i = 0; i < m; i++)
	{
		int s; cin >> s;
		vector<int> v;
		for(int i = 0; i < s; i++)
		{
			int w; cin >> w;
			--w;
			v.push_back(w);
		}
		sort(v.begin(), v.end(), comp);
		for(int i = 0; i < s; i++)
		{
			int a = v[i];
			int b = v[(i+1)%s];
			int c = lca(v[i], v[(i+1)%s]);
			upd(in[a], 1);
			upd(in[b], 1);
			upd(in[c], -2);
		}
	}
	vector<int> ans;
	for(int i = 0; i < n-1; i++)
	{
		pair<int, int> p = eg[i];
		if(in[p.first] > in[p.second]) swap(p.first, p.second);
		int ret = sum(ot[p.second]) - sum(in[p.second]-1);
		if(ret >= 2*k) ans.push_back(i+1);
	}
	cout << ans.size() << endl;
	for(int x : ans) cout << x << " ";
	cout << endl;
}

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