oj.uz

Submission #379676

# Submission time Handle Problem Language Result Execution time Memory
379676 2021-03-19T02:38:34 Z mode149256 Factories (JOI14_factories) C++17
33 / 100
 8000 ms 251600 KB 
/*input

*/
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#include "factories.h"
using namespace std;

namespace my_template {
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}
}
using namespace my_template;

const int MOD = 1000000007;
const ll INF = 1e14;
const int MX = 500101;
const int L = 19;

int n;
vector<vector<pair<int, ll>>> edges;
vi dep;
vl toRoot;
vii p;
vll w;
vi in;
vi out;
int piv;

void dfs(int x, int par) {
	in[x] = piv++;
	for (auto u : edges[x]) {
		if (u.x == par) continue;

		int b = u.x;
		dep[b] = dep[x] + 1;
		toRoot[b] = toRoot[x] + u.y;
		p[b][0] = x;
		w[b][0] = u.y;
		for (int i = 1; i < L; ++i)
		{
			p[b][i] = p[p[b][i - 1]][i - 1];
			w[b][i] = w[b][i - 1] + w[p[b][i - 1]][i - 1];
		}
		dfs(u.x, x);
	}
	out[x] = piv;
}

// a is ancestor of b
int anc(int a, int b) {
	return in[a] < in[b] and out[b] <= out[a];
}

int lca(int a, int b) {
	if (dep[a] > dep[b]) swap(a, b);

	// a
	// b
	for (int i = L - 1; i >= 0; --i)
	{
		if (dep[b] - (1 << i) >= dep[a])
			b = p[b][i];
	}
	assert(dep[a] == dep[b]);
	if (a == b) return a;

	for (int i = L - 1; i >= 0; i--)
	{
		if (p[a][i] != p[b][i]) {
			a = p[a][i];
			b = p[b][i];
		}
	}
	return p[a][0];
}

ll dis(int a, int b) {
	int l = lca(a, b);
	return toRoot[a] + toRoot[b] - 2 * toRoot[l];
}

void make_lca() {
	dep = vi(n);
	p = vii(n, vi(L, 0));
	w = vll(n, vl(L, 0));
	toRoot = vl(n);
	in = vi(n);
	out = vi(n);

	dep[0] = 0;
	p[0][0] = 0;
	w[0][0] = 0;
	toRoot[0] = 0;
	piv = 0;

	dfs(0, -1);
}
vi kas;

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	edges.resize(N);
	kas = vi(N, -1);
	for (int i = 0; i < N - 1; ++i)
	{
		int a = A[i];
		int b = B[i];
		int d = D[i];
		edges[a].emplace_back(b, d);
		edges[b].emplace_back(a, d);
	}

	make_lca();
}

ll Query(int S, int X[], int T, int Y[]) {
	vi visi;
	for (int i = 0; i < S; ++i) {
		visi.emplace_back(X[i]);
		kas[X[i]] = 1;
	}
	for (int i = 0; i < T; ++i) {
		visi.emplace_back(Y[i]);
		kas[Y[i]] = 2;
	}

	sort(visi.begin(), visi.end(), [&](const int & a, const int & b) {
		return in[a] < in[b];
	});

	for (int i = 1; i < S + T; ++i)
	{
		int l = lca(visi[i - 1], visi[i]);
		visi.emplace_back(l);
		if (kas[l] == -1)
			kas[l] = 0;
	}

	sort(visi.begin(), visi.end(), [&](const int & a, const int & b) {
		return in[a] < in[b];
	});

	visi.erase(unique(visi.begin(), visi.end()), visi.end());

	// print(visi);
	ll ats = INF;
	unordered_map<int, vl> low;
	vector<int> ver;

	ver.emplace_back(visi[0]);
	low[visi[0]] = vl{INF, INF};
	if (kas[visi[0]]) low[visi[0]][kas[visi[0]] - 1] = 0;

	for (int i = 1; i < (int)visi.size(); ++i)
	{
		while (!anc(ver.back(), visi[i])) {
			int a = ver.back(); ver.pop_back();
			int b = ver.back();

			ll d = dis(a, b);
			if (kas[a] + kas[b] == 3)
				ats = min(ats, d);

			//   b
			//  /  c
			// a

			low[b][0] = min(low[b][0], low[a][0] + d);
			low[b][1] = min(low[b][1], low[a][1] + d);
		}
		ver.emplace_back(visi[i]);
		low[visi[i]] = vl{INF, INF};
		if (kas[visi[i]]) low[visi[i]][kas[visi[i]] - 1] = 0;
	}

	while (ver.size() >= 2) {
		int a = ver.back(); ver.pop_back();
		int b = ver.back();
		ll d = dis(a, b);
		// printf("a = %d, b = %d, d = %lld\n", a, b, d);
		if (kas[a] + kas[b] == 3)
			ats = min(ats, d);

		//   b
		//  /  c
		// a

		low[b][0] = min(low[b][0], low[a][0] + d);
		low[b][1] = min(low[b][1], low[a][1] + d);
	}

	for (auto u : visi) {
		// printf("u = %d, low = %lld %lld\n", u, low[u][0], low[u][1]);
		ats = min(ats, low[u][0] + low[u][1]);
		kas[u] = -1;
	}
	return ats;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1004 KB Output is correct
2 Correct 1845 ms 10936 KB Output is correct
3 Correct 2076 ms 10924 KB Output is correct
4 Correct 1932 ms 11212 KB Output is correct
5 Correct 1665 ms 11340 KB Output is correct
6 Correct 1346 ms 11100 KB Output is correct
7 Correct 2070 ms 10988 KB Output is correct
8 Correct 1956 ms 11268 KB Output is correct
9 Correct 1660 ms 11380 KB Output is correct
10 Correct 1339 ms 11060 KB Output is correct
11 Correct 2065 ms 10732 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 620 KB Output is correct
2 Correct 3146 ms 211096 KB Output is correct
3 Correct 5580 ms 215020 KB Output is correct
4 Correct 2102 ms 208732 KB Output is correct
5 Correct 5148 ms 245424 KB Output is correct
6 Correct 6052 ms 216248 KB Output is correct
7 Correct 5573 ms 51404 KB Output is correct
8 Correct 2123 ms 64904 KB Output is correct
9 Correct 4630 ms 69868 KB Output is correct
10 Correct 5625 ms 66540 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1004 KB Output is correct
2 Correct 1845 ms 10936 KB Output is correct
3 Correct 2076 ms 10924 KB Output is correct
4 Correct 1932 ms 11212 KB Output is correct
5 Correct 1665 ms 11340 KB Output is correct
6 Correct 1346 ms 11100 KB Output is correct
7 Correct 2070 ms 10988 KB Output is correct
8 Correct 1956 ms 11268 KB Output is correct
9 Correct 1660 ms 11380 KB Output is correct
10 Correct 1339 ms 11060 KB Output is correct
11 Correct 2065 ms 10732 KB Output is correct
12 Correct 6 ms 620 KB Output is correct
13 Correct 3146 ms 211096 KB Output is correct
14 Correct 5580 ms 215020 KB Output is correct
15 Correct 2102 ms 208732 KB Output is correct
16 Correct 5148 ms 245424 KB Output is correct
17 Correct 6052 ms 216248 KB Output is correct
18 Correct 5573 ms 51404 KB Output is correct
19 Correct 2123 ms 64904 KB Output is correct
20 Correct 4630 ms 69868 KB Output is correct
21 Correct 5625 ms 66540 KB Output is correct
22 Correct 7007 ms 247492 KB Output is correct
23 Correct 5935 ms 249432 KB Output is correct
24 Execution timed out 8080 ms 251600 KB Time limit exceeded
25 Halted 0 ms 0 KB -