oj.uz

Submission #381679

# Submission time Handle Problem Language Result Execution time Memory
381679 2021-03-25T15:41:28 Z peijar Valley (BOI19_valley) C++17
23 / 100
 243 ms 44124 KB 
#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);
	}
	vector<int> magasins(nbMagasins);
	for (auto &v : magasins)
	{
		cin >> v;
		--v;
		estMagasin[v] = 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);
			for (int p(0); p < MAXP; ++p)
				if ((1<<p) & diff)
				{
					ret = min(ret, meilleurParMagasins[p][iSommet]);
					int nxt = par[p][iSommet];
					coutCumul += profPoids[iSommet] - profPoids[nxt];
					iSommet = nxt;
				}
			if (ret == INF)
				cout << "oo";
			else
				cout << ret;
		}
		cout << '\n';
	}
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 3052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 3052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 39900 KB Output is correct
2 Correct 161 ms 39772 KB Output is correct
3 Correct 167 ms 39900 KB Output is correct
4 Correct 193 ms 41808 KB Output is correct
5 Correct 188 ms 42076 KB Output is correct
6 Correct 243 ms 44124 KB Output is correct

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 3052 KB Output isn't correct
2 Halted 0 ms 0 KB -