oj.uz

Submission #374980

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

vector<vector<pair<int, int>>> g;
int nbSommets;
vector<int> tempsDeb, tempsFin;
vector<int> depthWeight, depth;
vector<int> eulerTour;
vector<int> posEuler;
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;

		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 int MAXP = 21;

struct Sparse
{
	pair<int, int> sparse[MAXP][1 << MAXP];
	int 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)))]);
	}

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

Sparse sparse;


void dfs(int u, int p=0)
{
	tempsDeb[u] = temps++;
	posEuler[u] = (int)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);
			posEuler[u] = (int)eulerTour.size();
			eulerTour.push_back(u);
		}
	tempsFin[u] = temps++;
}

int calcLca(int u, int 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 (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);
	sparse.build();
	cerr << "finished init" << endl;
}

vector<int> potentielsLca;
vector<int> sommetsRequete;

int Query(signed S, signed X[], signed T, signed Y[]) {
	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 tempsDeb[u]< tempsDeb[v];
			});
	potentielsLca.reserve((int)sommetsRequete.size()  - 1);
	for (int i(1); i < (int)sommetsRequete.size(); ++i)
		potentielsLca.push_back(calcLca(sommetsRequete[i-1], sommetsRequete[i]));
	sommetsRequete.clear();
	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]);
	}
	potentielsLca.clear();

	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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 266 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 263 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Runtime error 266 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -