oj.uz

Submission #374986

# Submission time Handle Problem Language Result Execution time Memory
374986 2021-03-08T18:23:32 Z peijar Factories (JOI14_factories) C++17
100 / 100
 3727 ms 524288 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<signed, signed> 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];
		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);
			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();
}

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

# Verdict Execution time Memory Grader output
1 Correct 228 ms 395116 KB Output is correct
2 Correct 1020 ms 404180 KB Output is correct
3 Correct 1130 ms 404076 KB Output is correct
4 Correct 1098 ms 404204 KB Output is correct
5 Correct 1154 ms 404460 KB Output is correct
6 Correct 979 ms 404332 KB Output is correct
7 Correct 1132 ms 404120 KB Output is correct
8 Correct 1109 ms 404056 KB Output is correct
9 Correct 1160 ms 404504 KB Output is correct
10 Correct 1008 ms 404076 KB Output is correct
11 Correct 1138 ms 404204 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 394476 KB Output is correct
2 Correct 1858 ms 472176 KB Output is correct
3 Correct 2236 ms 476632 KB Output is correct
4 Correct 1565 ms 469820 KB Output is correct
5 Correct 2310 ms 499976 KB Output is correct
6 Correct 2325 ms 476664 KB Output is correct
7 Correct 2371 ms 419588 KB Output is correct
8 Correct 1617 ms 419524 KB Output is correct
9 Correct 2450 ms 423516 KB Output is correct
10 Correct 2324 ms 421068 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 395116 KB Output is correct
2 Correct 1020 ms 404180 KB Output is correct
3 Correct 1130 ms 404076 KB Output is correct
4 Correct 1098 ms 404204 KB Output is correct
5 Correct 1154 ms 404460 KB Output is correct
6 Correct 979 ms 404332 KB Output is correct
7 Correct 1132 ms 404120 KB Output is correct
8 Correct 1109 ms 404056 KB Output is correct
9 Correct 1160 ms 404504 KB Output is correct
10 Correct 1008 ms 404076 KB Output is correct
11 Correct 1138 ms 404204 KB Output is correct
12 Correct 212 ms 394476 KB Output is correct
13 Correct 1858 ms 472176 KB Output is correct
14 Correct 2236 ms 476632 KB Output is correct
15 Correct 1565 ms 469820 KB Output is correct
16 Correct 2310 ms 499976 KB Output is correct
17 Correct 2325 ms 476664 KB Output is correct
18 Correct 2371 ms 419588 KB Output is correct
19 Correct 1617 ms 419524 KB Output is correct
20 Correct 2450 ms 423516 KB Output is correct
21 Correct 2324 ms 421068 KB Output is correct
22 Correct 3199 ms 475776 KB Output is correct
23 Correct 2980 ms 478408 KB Output is correct
24 Correct 3422 ms 479908 KB Output is correct
25 Correct 3382 ms 482740 KB Output is correct
26 Correct 3727 ms 477384 KB Output is correct
27 Correct 3330 ms 524288 KB Output is correct
28 Correct 2602 ms 500968 KB Output is correct
29 Correct 3584 ms 501464 KB Output is correct
30 Correct 3610 ms 500932 KB Output is correct
31 Correct 3647 ms 501320 KB Output is correct
32 Correct 1820 ms 439480 KB Output is correct
33 Correct 1543 ms 434984 KB Output is correct
34 Correct 1942 ms 430180 KB Output is correct
35 Correct 1873 ms 430200 KB Output is correct
36 Correct 2213 ms 431196 KB Output is correct
37 Correct 2209 ms 431092 KB Output is correct