Submission #384104

#	Time	Username	Problem	Language	Result	Execution time	Memory
384104		peijar	Railway (BOI17_railway)	C++17	100 / 100	277 ms	35168 KiB

railway

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

const int MAXN = 1e5;
const int MAXP = 18;

int par[MAXP][MAXN];
int parEdge[MAXN];
int nbMarque[MAXN];
vector<pair<int, int>> adj[MAXN];
int delta[MAXN];
int depth[MAXN];
int t;
int tin[MAXN];
int nbSommets, nbDeputes, nbVoulu;

void dfs(int iNoeud, int iPere)
{
	par[0][iNoeud] = iPere;
	tin[iNoeud] = t++;
	for (auto [iFrere, iArete] : adj[iNoeud])
		if (iFrere != iPere)
		{
			parEdge[iFrere] = iArete;
			depth[iFrere] = depth[iNoeud] + 1;
			dfs(iFrere, iNoeud);
		}
}

void init()
{
	for (int p = 0; p < MAXP-1; ++p) 
		for (int iSommet = 0; iSommet < nbSommets; ++iSommet) 
			par[p+1][iSommet] = par[p][par[p][iSommet]];
}

int calcLca(int a, int b)
{
	if (depth[a] < depth[b]) swap(a, b);
	int diff = depth[a] - depth[b];
	for (int p = 0; p < MAXP; ++p) 
		if ((1<<p) & diff)
			a = par[p][a];
	if(a == b) return a;
	for (int p(MAXP-1); p >= 0; --p)
		if (par[p][a] != par[p][b])
			a = par[p][a], b = par[p][b];
	return par[0][a];
}

int dfs2(int iNoeud)
{
	for (auto [iFrere, iArete] : adj[iNoeud])
		if (iFrere != par[0][iNoeud])
			delta[iNoeud] += dfs2(iFrere);
	
	if (iNoeud)
		nbMarque[parEdge[iNoeud]] += delta[iNoeud];
	return delta[iNoeud];
}

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> nbSommets >> nbDeputes >> nbVoulu;
	for (int iArete(0); iArete < nbSommets-1; ++iArete)
	{
		int u, v;
		cin >> u >> v;
		--u, --v;
		adj[u].emplace_back(v, iArete);
		adj[v].emplace_back(u, iArete);
	}
	dfs(0, 0);
	init();
	
	for (int iDepute = 0; iDepute < nbDeputes; ++iDepute) 
	{
		int nbVilles;
		cin>> nbVilles;
		vector<int> villes(nbVilles);
		for (auto &v : villes) {cin >> v; --v;};
		sort(villes.begin(), villes.end(), [&](int i, int j) {return tin[i] < tin[j];});
		villes.push_back(villes[0]);
		for (int i(0); i < nbVilles; ++i)
		{
			int lca = calcLca(villes[i], villes[i+1]);
			delta[villes[i]]++; delta[villes[i+1]]++;
			delta[lca]-=2;
		}
	}
	assert(!dfs2(0));
	vector<int> sol;
	for (int iArete(0); iArete < nbSommets-1; ++iArete)
		if (nbMarque[iArete] >= 2*nbVoulu)
			sol.push_back(iArete);
	cout << sol.size() << endl;
	for (auto iArete : sol)
		cout << iArete + 1 << ' ';
	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