Submission #381680

#	Time	Username	Problem	Language	Result	Execution time	Memory
381680		peijar	Valley (BOI19_valley)	C++17	100 / 100	252 ms	47580 KiB

valley

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

const int MAXN = 1e5;
const int MAXP = 17;
const int INF = 1e18;

vector<pair<int, int>> adj[MAXN];
int profondeur[MAXN];
int profPoids[MAXN];
int meilleurMagasins[MAXN];
int meilleurParMagasins[MAXP][MAXN];
int par[MAXP][MAXN];
bool estMagasin[MAXN];
int nbVilles;
vector<pair<int, int>> aretes;

void dfs(int iNoeud, int iPere=-1)
{
	if (iPere == -1)
		par[0][iNoeud] = iNoeud;
	if (!estMagasin[iNoeud])
		meilleurMagasins[iNoeud] = INF;

	for (auto [iFrere, poids] : adj[iNoeud])
		if (iFrere != iPere)
		{
			par[0][iFrere] = iNoeud;
			profondeur[iFrere] = profondeur[iNoeud] + 1;
			profPoids[iFrere] = profPoids[iNoeud] + poids;
			dfs(iFrere, iNoeud);
			meilleurMagasins[iNoeud] = min(meilleurMagasins[iNoeud], poids + meilleurMagasins[iFrere]);
		}
}

void init()
{
	for (int p = 0; p < MAXP-1; ++p) 
		for (int iNoeud = 0; iNoeud < nbVilles; ++iNoeud) 
			par[p+1][iNoeud] = par[p][par[p][iNoeud]];
	for (int p = 0; p < MAXP; ++p) 
		for (int iNoeud = 0; iNoeud < nbVilles; ++iNoeud) 
		{
			if (p == 0)
				meilleurParMagasins[p][iNoeud] = min(INF, 
						meilleurMagasins[par[0][iNoeud]] + profPoids[iNoeud] - profPoids[par[0][iNoeud]]);
			else
				meilleurParMagasins[p][iNoeud] = min(meilleurParMagasins[p-1][iNoeud],
						meilleurParMagasins[p-1][par[p-1][iNoeud]] + profPoids[iNoeud] - profPoids[par[p-1][iNoeud]]);
		}
}

int monte(int iNoeud, int dis)
{
	for (int p(0); p < MAXP; ++p)
		if ((1<<p) & dis)
			iNoeud = par[p][iNoeud];
	return iNoeud;
}

bool estAncetre(int iNoeud, int iAncetre)
{
	int delta = profondeur[iNoeud] - profondeur[iAncetre];
	return delta >= 0 and monte(iNoeud, delta) == iAncetre;
}

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int nbMagasins, nbRequetes, racine;
	cin >> nbVilles >> nbMagasins >> nbRequetes >> racine;
	--racine;
	for (int i = 0; i < nbVilles-1; ++i) 
	{
		int u, v, w;
		cin >> u >> v >> w;
		--u, --v;
		aretes.emplace_back(u, v);
		adj[u].emplace_back(v, w);
		adj[v].emplace_back(u, w);
	}
	for (int iMagasin = 0; iMagasin < nbMagasins; ++iMagasin) 
	{
		int pos;
		cin >> pos;
		estMagasin[pos-1] = true;
	}

	dfs(racine);
	init();
	for (int iRequete = 0; iRequete < nbRequetes; ++iRequete) 
	{
		int iArete, iSommet;
		cin >> iArete >> iSommet;
		--iArete, --iSommet;
		auto [u, v] = aretes[iArete];
		if (profondeur[u] < profondeur[v]) swap(u, v);
		if (!estAncetre(iSommet, u))
			cout << "escaped";
		else
		{
			int diff = profondeur[iSommet] - profondeur[u];
			int ret = meilleurMagasins[iSommet];
			int coutCumul(0);
			//cout << iSommet << ' ' << ret << endl;
			for (int p(0); p < MAXP; ++p)
				if ((1<<p) & diff)
				{
					ret = min(ret, meilleurParMagasins[p][iSommet]+coutCumul);
					int nxt = par[p][iSommet];
					coutCumul += profPoids[iSommet] - profPoids[nxt];
					iSommet = nxt;
					//cout << iSommet << ' ' << ret << ' ' << coutCumul << endl;
				}
			if (ret == INF)
				cout << "oo";
			else
				cout << ret;
		}
		cout << '\n';
	}
}

• Subtask 1: 9 / 9
• Subtask 2: 27 / 27
• Subtask 3: 23 / 23
• Subtask 4: 41 / 41