oj.uz

Submission #374972

# Submission time Handle Problem Language Result Execution time Memory
374972 2021-03-08T17:31:17 Z peijar Factories (JOI14_factories) C++17
33 / 100
 8000 ms 288424 KB 
#include "factories.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int MAXP = 20;
vector<vector<pair<int, int>>> g;
int nbSommets;
vector<int> tempsDeb, tempsFin;
vector<int> par[MAXP], parWeight[MAXP];
vector<int> depthWeight, depth;
int temps;
const int nbFeuilles = 1 << 20;
const int INF = 1e18;

struct Segtree
{
	int seg[2 * nbFeuilles];

	Segtree()
	{
		for (int i(0); i < 2 * nbFeuilles; ++i)
			seg[i] = INF;
	}

	void update(int pos, int val)
	{
		pos += nbFeuilles;
		seg[pos] = val;
		while (pos > 1)
		{
			pos /= 2;
			seg[pos] = min(seg[2*pos], seg[2*pos+1]);
		}
	}

	int query(int deb, int fin)
	{
		deb += nbFeuilles, fin += nbFeuilles;
		int ret = INF;

		/*
		 * 1
		 * 2 3
		 * 4 5 6 7
		 */
		while (deb < fin)
		{
			if (deb % 2)
				ret = min(ret, seg[deb]);
			deb = (deb + 1)/2;
			if (fin % 2 == 0)
				ret = min(ret, seg[fin]);
			fin = (fin - 1) / 2;
		}
		if (deb == fin)
			ret = min(ret, seg[deb]);
		return ret;
	}
};

Segtree seg1, seg2;


void dfs(int u)
{
	tempsDeb[u] = temps++;
	for (auto [v,w] : g[u])
		if (v != par[0][u])
		{
			par[0][v] = u;
			parWeight[0][v] = w;
			depth[v] = depth[u] + 1;
			depthWeight[v] = depthWeight[u] + w;
			dfs(v);
		}
	tempsFin[u] = temps++;
}

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

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

int calcDis(int u, int v)
{
	return depthWeight[u] + depthWeight[v] - 2 * depthWeight[calcLca(u, v)];
}

void Init(signed N, signed A[], signed B[], signed D[]) 
{
	nbSommets = N;
	g.resize(nbSommets);
	tempsDeb.resize(nbSommets);
	tempsFin.resize(nbSommets);
	depth.resize(nbSommets);
	depthWeight.resize(nbSommets);
	for (int p(0); p < MAXP; ++p)
		par[p].resize(nbSommets), parWeight[p].resize(nbSommets);
	for (int i(0); i < N-1; ++i)
	{
		g[A[i]].emplace_back(B[i], D[i]);
		g[B[i]].emplace_back(A[i], D[i]);
	}
	temps = 0;
	dfs(0);
	initLca();
}

int Query(signed S, signed X[], signed T, signed Y[]) {
	vector<int> sommetsRequete;
	for (int i(0); i < S; ++i)
		sommetsRequete.push_back(X[i]);
	for (int i(0); i < T; ++i)
		sommetsRequete.push_back(Y[i]);
	sort(sommetsRequete.begin(), sommetsRequete.end(),
			[&](int u, int v)
			{
				return make_pair(tempsDeb[u], u) < make_pair(tempsDeb[v], v);
			});
	vector<int> potentielsLca;
	/*for (int i(0); i < S; ++i)
		potentielsLca.push_back(X[i]);
	for (int i(0); i < T; ++i)
		potentielsLca.push_back(Y[i]);*/
	for (int i(1); i < (int)sommetsRequete.size(); ++i)
		potentielsLca.push_back(calcLca(sommetsRequete[i-1], sommetsRequete[i]));
	int ret = INF;
	for (int i(0); i < S; ++i)
		seg1.update(tempsDeb[X[i]], depthWeight[X[i]]);
	for (int i(0); i < T; ++i)
		seg2.update(tempsDeb[Y[i]], depthWeight[Y[i]]);
	for (auto lca : potentielsLca)
	{
		ret = min(ret, seg1.query(tempsDeb[lca], tempsFin[lca])
				+ seg2.query(tempsDeb[lca], tempsFin[lca])
				- 2 * depthWeight[lca]);
	}

	for (int i(0); i < T; ++i)
		seg2.update(tempsDeb[Y[i]], INF);
	for (int i(0); i < S; ++i)
		seg1.update(tempsDeb[X[i]], INF);
	return ret;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 33900 KB Output is correct
2 Correct 1411 ms 43884 KB Output is correct
3 Correct 1612 ms 44204 KB Output is correct
4 Correct 1504 ms 44208 KB Output is correct
5 Correct 1588 ms 44364 KB Output is correct
6 Correct 1412 ms 44140 KB Output is correct
7 Correct 1611 ms 44348 KB Output is correct
8 Correct 1531 ms 44440 KB Output is correct
9 Correct 1567 ms 44268 KB Output is correct
10 Correct 1430 ms 44140 KB Output is correct
11 Correct 1591 ms 44124 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 33516 KB Output is correct
2 Correct 4418 ms 255652 KB Output is correct
3 Correct 5350 ms 258796 KB Output is correct
4 Correct 4009 ms 253388 KB Output is correct
5 Correct 5458 ms 276588 KB Output is correct
6 Correct 5671 ms 259224 KB Output is correct
7 Correct 7651 ms 86960 KB Output is correct
8 Correct 5744 ms 86780 KB Output is correct
9 Correct 6768 ms 90220 KB Output is correct
10 Correct 7141 ms 88044 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 33900 KB Output is correct
2 Correct 1411 ms 43884 KB Output is correct
3 Correct 1612 ms 44204 KB Output is correct
4 Correct 1504 ms 44208 KB Output is correct
5 Correct 1588 ms 44364 KB Output is correct
6 Correct 1412 ms 44140 KB Output is correct
7 Correct 1611 ms 44348 KB Output is correct
8 Correct 1531 ms 44440 KB Output is correct
9 Correct 1567 ms 44268 KB Output is correct
10 Correct 1430 ms 44140 KB Output is correct
11 Correct 1591 ms 44124 KB Output is correct
12 Correct 23 ms 33516 KB Output is correct
13 Correct 4418 ms 255652 KB Output is correct
14 Correct 5350 ms 258796 KB Output is correct
15 Correct 4009 ms 253388 KB Output is correct
16 Correct 5458 ms 276588 KB Output is correct
17 Correct 5671 ms 259224 KB Output is correct
18 Correct 7651 ms 86960 KB Output is correct
19 Correct 5744 ms 86780 KB Output is correct
20 Correct 6768 ms 90220 KB Output is correct
21 Correct 7141 ms 88044 KB Output is correct
22 Correct 7545 ms 259424 KB Output is correct
23 Correct 7568 ms 260968 KB Output is correct
24 Correct 7845 ms 262260 KB Output is correct
25 Execution timed out 8076 ms 288424 KB Time limit exceeded
26 Halted 0 ms 0 KB -