oj.uz

Submission #374977

# Submission time Handle Problem Language Result Execution time Memory
374977 2021-03-08T17:44:11 Z peijar Factories (JOI14_factories) C++17
33 / 100
 8000 ms 284268 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;

		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]];
}

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;
}

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();
	cerr << "finished init" << endl;
}

vector<int> potentielsLca;

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 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]));
	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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 33644 KB Output is correct
2 Correct 1363 ms 43520 KB Output is correct
3 Correct 1568 ms 43596 KB Output is correct
4 Correct 1458 ms 43840 KB Output is correct
5 Correct 1505 ms 43884 KB Output is correct
6 Correct 1341 ms 43500 KB Output is correct
7 Correct 1552 ms 43548 KB Output is correct
8 Correct 1466 ms 43628 KB Output is correct
9 Correct 1508 ms 43756 KB Output is correct
10 Correct 1355 ms 43628 KB Output is correct
11 Correct 1555 ms 43628 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 4153 ms 255792 KB Output is correct
3 Correct 5153 ms 258068 KB Output is correct
4 Correct 3865 ms 253512 KB Output is correct
5 Correct 5134 ms 276972 KB Output is correct
6 Correct 5376 ms 259464 KB Output is correct
7 Correct 7209 ms 86276 KB Output is correct
8 Correct 5409 ms 86524 KB Output is correct
9 Correct 6822 ms 90084 KB Output is correct
10 Correct 7314 ms 87948 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 33644 KB Output is correct
2 Correct 1363 ms 43520 KB Output is correct
3 Correct 1568 ms 43596 KB Output is correct
4 Correct 1458 ms 43840 KB Output is correct
5 Correct 1505 ms 43884 KB Output is correct
6 Correct 1341 ms 43500 KB Output is correct
7 Correct 1552 ms 43548 KB Output is correct
8 Correct 1466 ms 43628 KB Output is correct
9 Correct 1508 ms 43756 KB Output is correct
10 Correct 1355 ms 43628 KB Output is correct
11 Correct 1555 ms 43628 KB Output is correct
12 Correct 23 ms 33516 KB Output is correct
13 Correct 4153 ms 255792 KB Output is correct
14 Correct 5153 ms 258068 KB Output is correct
15 Correct 3865 ms 253512 KB Output is correct
16 Correct 5134 ms 276972 KB Output is correct
17 Correct 5376 ms 259464 KB Output is correct
18 Correct 7209 ms 86276 KB Output is correct
19 Correct 5409 ms 86524 KB Output is correct
20 Correct 6822 ms 90084 KB Output is correct
21 Correct 7314 ms 87948 KB Output is correct
22 Correct 7581 ms 259756 KB Output is correct
23 Correct 7523 ms 261636 KB Output is correct
24 Correct 7753 ms 263300 KB Output is correct
25 Correct 7813 ms 266012 KB Output is correct
26 Execution timed out 8090 ms 284268 KB Time limit exceeded
27 Halted 0 ms 0 KB -