oj.uz

Submission #374970

# Submission time Handle Problem Language Result Execution time Memory
374970 2021-03-08T17:29:13 Z peijar Factories (JOI14_factories) C++17
33 / 100
 8000 ms 295352 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 45 ms 33644 KB Output is correct
2 Correct 1513 ms 43688 KB Output is correct
3 Correct 1755 ms 52996 KB Output is correct
4 Correct 1688 ms 53248 KB Output is correct
5 Correct 1951 ms 53376 KB Output is correct
6 Correct 1447 ms 53100 KB Output is correct
7 Correct 1755 ms 52972 KB Output is correct
8 Correct 1706 ms 53264 KB Output is correct
9 Correct 1958 ms 53216 KB Output is correct
10 Correct 1446 ms 53100 KB Output is correct
11 Correct 1820 ms 53104 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 4465 ms 255976 KB Output is correct
3 Correct 5439 ms 268124 KB Output is correct
4 Correct 4027 ms 271716 KB Output is correct
5 Correct 5658 ms 295352 KB Output is correct
6 Correct 5766 ms 277992 KB Output is correct
7 Correct 7698 ms 100376 KB Output is correct
8 Correct 5587 ms 100576 KB Output is correct
9 Correct 7350 ms 103776 KB Output is correct
10 Correct 7526 ms 101740 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 33644 KB Output is correct
2 Correct 1513 ms 43688 KB Output is correct
3 Correct 1755 ms 52996 KB Output is correct
4 Correct 1688 ms 53248 KB Output is correct
5 Correct 1951 ms 53376 KB Output is correct
6 Correct 1447 ms 53100 KB Output is correct
7 Correct 1755 ms 52972 KB Output is correct
8 Correct 1706 ms 53264 KB Output is correct
9 Correct 1958 ms 53216 KB Output is correct
10 Correct 1446 ms 53100 KB Output is correct
11 Correct 1820 ms 53104 KB Output is correct
12 Correct 23 ms 33516 KB Output is correct
13 Correct 4465 ms 255976 KB Output is correct
14 Correct 5439 ms 268124 KB Output is correct
15 Correct 4027 ms 271716 KB Output is correct
16 Correct 5658 ms 295352 KB Output is correct
17 Correct 5766 ms 277992 KB Output is correct
18 Correct 7698 ms 100376 KB Output is correct
19 Correct 5587 ms 100576 KB Output is correct
20 Correct 7350 ms 103776 KB Output is correct
21 Correct 7526 ms 101740 KB Output is correct
22 Correct 7752 ms 285984 KB Output is correct
23 Correct 7976 ms 286976 KB Output is correct
24 Execution timed out 8103 ms 289060 KB Time limit exceeded
25 Halted 0 ms 0 KB -