oj.uz

Submission #374987

# Submission time Handle Problem Language Result Execution time Memory
374987 2021-03-08T18:29:05 Z peijar Factories (JOI14_factories) C++17
100 / 100
 3496 ms 482600 KB 
#include "factories.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<vector<pair<int, int>>> g;
signed nbSommets;
vector<signed> tempsDeb, tempsFin;
vector<int> depthWeight, depth;
vector<signed> eulerTour;
vector<signed> posEuler;
signed temps;
const signed 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(signed deb, signed fin)
	{
		deb += nbFeuilles, fin += nbFeuilles;
		int ret = INF;

		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;

const signed MAXP = 21;

struct Sparse
{
	pair<signed, signed> sparse[MAXP][1 << MAXP];
	signed log2[1 << MAXP];

	void build()
	{
		log2[1] = 0;
		for (int i(2); i < (1 << MAXP); ++i)
			log2[i] = 1 + log2[i/2];
		for (int i(0); i < (int)eulerTour.size(); ++i)
			sparse[0][i] = make_pair(depth[eulerTour[i]], eulerTour[i]);
		for (int p(1); p < MAXP; ++p)
			for (int i(0); i < (int)eulerTour.size(); ++i)
				sparse[p][i] = min(sparse[p-1][i],
						sparse[p-1][min((int)eulerTour.size()-1, i + (1 << (p-1)))]);
	}

	signed getMin(signed deb, signed fin)
	{
		if (deb > fin) swap(deb, fin);
		signed lg = log2[fin-deb+1];
		return min(sparse[lg][deb], sparse[lg][fin - (1<<lg)+1]).second;
	}
};

Sparse sparse;


void dfs(signed u, int p=0)
{
	tempsDeb[u] = temps++;
	posEuler[u] = (signed)eulerTour.size();
	eulerTour.push_back(u);
	for (auto [v,w] : g[u])
		if (v != p)
		{
			depth[v] = depth[u] + 1;
			depthWeight[v] = depthWeight[u] + w;
			dfs(v, u);
			eulerTour.push_back(u);
		}
	tempsFin[u] = temps++;
}

signed calcLca(signed u, signed v)
{
	return sparse.getMin(posEuler[u], posEuler[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);
	posEuler.resize(nbSommets);
	for (signed 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);
	sparse.build();
}

vector<signed> potentielsLca;
vector<signed> sommetsRequete;

int Query(signed S, signed X[], signed T, signed Y[]) {
	for (signed i(0); i < S; ++i)
		sommetsRequete.push_back(X[i]);
	for (signed i(0); i < T; ++i)
		sommetsRequete.push_back(Y[i]);
	sort(sommetsRequete.begin(), sommetsRequete.end(),
			[&](signed u, signed v)
			{
				return tempsDeb[u]< tempsDeb[v];
			});
	potentielsLca.reserve((signed)sommetsRequete.size()  - 1);
	for (signed i(1); i < (signed)sommetsRequete.size(); ++i)
		potentielsLca.push_back(calcLca(sommetsRequete[i-1], sommetsRequete[i]));
	sommetsRequete.clear();
	int ret = INF;
	for (signed i(0); i < S; ++i)
		seg1.update(tempsDeb[X[i]], depthWeight[X[i]]);
	for (signed 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]);
	}
	potentielsLca.clear();

	for (signed i(0); i < T; ++i)
		seg2.update(tempsDeb[Y[i]], INF);
	for (signed 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 226 ms 386796 KB Output is correct
2 Correct 1024 ms 395500 KB Output is correct
3 Correct 1121 ms 395576 KB Output is correct
4 Correct 1089 ms 395504 KB Output is correct
5 Correct 1179 ms 395596 KB Output is correct
6 Correct 982 ms 395372 KB Output is correct
7 Correct 1123 ms 395536 KB Output is correct
8 Correct 1093 ms 395516 KB Output is correct
9 Correct 1150 ms 395840 KB Output is correct
10 Correct 968 ms 395500 KB Output is correct
11 Correct 1125 ms 395504 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 386304 KB Output is correct
2 Correct 1796 ms 454400 KB Output is correct
3 Correct 2195 ms 458192 KB Output is correct
4 Correct 1483 ms 455988 KB Output is correct
5 Correct 2241 ms 481780 KB Output is correct
6 Correct 2253 ms 458596 KB Output is correct
7 Correct 2085 ms 409096 KB Output is correct
8 Correct 1470 ms 409852 KB Output is correct
9 Correct 2073 ms 412872 KB Output is correct
10 Correct 2016 ms 410512 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 386796 KB Output is correct
2 Correct 1024 ms 395500 KB Output is correct
3 Correct 1121 ms 395576 KB Output is correct
4 Correct 1089 ms 395504 KB Output is correct
5 Correct 1179 ms 395596 KB Output is correct
6 Correct 982 ms 395372 KB Output is correct
7 Correct 1123 ms 395536 KB Output is correct
8 Correct 1093 ms 395516 KB Output is correct
9 Correct 1150 ms 395840 KB Output is correct
10 Correct 968 ms 395500 KB Output is correct
11 Correct 1125 ms 395504 KB Output is correct
12 Correct 211 ms 386304 KB Output is correct
13 Correct 1796 ms 454400 KB Output is correct
14 Correct 2195 ms 458192 KB Output is correct
15 Correct 1483 ms 455988 KB Output is correct
16 Correct 2241 ms 481780 KB Output is correct
17 Correct 2253 ms 458596 KB Output is correct
18 Correct 2085 ms 409096 KB Output is correct
19 Correct 1470 ms 409852 KB Output is correct
20 Correct 2073 ms 412872 KB Output is correct
21 Correct 2016 ms 410512 KB Output is correct
22 Correct 3007 ms 456748 KB Output is correct
23 Correct 2799 ms 459560 KB Output is correct
24 Correct 3215 ms 460520 KB Output is correct
25 Correct 3216 ms 463828 KB Output is correct
26 Correct 3496 ms 459504 KB Output is correct
27 Correct 3209 ms 482600 KB Output is correct
28 Correct 2500 ms 459848 KB Output is correct
29 Correct 3477 ms 458924 KB Output is correct
30 Correct 3464 ms 458472 KB Output is correct
31 Correct 3490 ms 459232 KB Output is correct
32 Correct 1653 ms 414560 KB Output is correct
33 Correct 1444 ms 410204 KB Output is correct
34 Correct 1744 ms 406832 KB Output is correct
35 Correct 1783 ms 406792 KB Output is correct
36 Correct 2025 ms 407396 KB Output is correct
37 Correct 2007 ms 407388 KB Output is correct