oj.uz

Submission #379683

# Submission time Handle Problem Language Result Execution time Memory
379683 2021-03-19T02:51:33 Z mode149256 Factories (JOI14_factories) C++17
15 / 100
 5042 ms 263768 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 = 18;

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

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();
	low = vll(n, vl{INF, INF});
}

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)
	{
		if (anc(visi[i - 1], visi[i]) or anc(visi[i], visi[i - 1])) continue;

		int l = lca(visi[i - 1], visi[i]);
		if (kas[l] == -1) {
			visi.emplace_back(l);
			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;

	stack<int> ver;

	ver.push(visi[0]);
	if (kas[visi[0]]) low[visi[0]][kas[visi[0]] - 1] = 0;

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

			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.push(visi[i]);
		if (kas[visi[i]]) low[visi[i]][kas[visi[i]] - 1] = 0;
	}

	while (ver.size() >= 2) {
		int a = ver.top(); ver.pop();
		int b = ver.top();
		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;
		low[u][0] = low[u][1] = INF;
	}
	return ats;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 876 KB Output is correct
2 Correct 1083 ms 10732 KB Output is correct
3 Correct 1188 ms 10604 KB Output is correct
4 Correct 1129 ms 11008 KB Output is correct
5 Correct 1123 ms 10988 KB Output is correct
6 Correct 1014 ms 10564 KB Output is correct
7 Correct 1205 ms 10588 KB Output is correct
8 Correct 1103 ms 10732 KB Output is correct
9 Correct 1348 ms 10988 KB Output is correct
10 Correct 992 ms 10712 KB Output is correct
11 Correct 2052 ms 10624 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 620 KB Output is correct
2 Correct 2959 ms 230640 KB Output is correct
3 Correct 5042 ms 233312 KB Output is correct
4 Correct 1843 ms 228268 KB Output is correct
5 Incorrect 4673 ms 263768 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 876 KB Output is correct
2 Correct 1083 ms 10732 KB Output is correct
3 Correct 1188 ms 10604 KB Output is correct
4 Correct 1129 ms 11008 KB Output is correct
5 Correct 1123 ms 10988 KB Output is correct
6 Correct 1014 ms 10564 KB Output is correct
7 Correct 1205 ms 10588 KB Output is correct
8 Correct 1103 ms 10732 KB Output is correct
9 Correct 1348 ms 10988 KB Output is correct
10 Correct 992 ms 10712 KB Output is correct
11 Correct 2052 ms 10624 KB Output is correct
12 Correct 4 ms 620 KB Output is correct
13 Correct 2959 ms 230640 KB Output is correct
14 Correct 5042 ms 233312 KB Output is correct
15 Correct 1843 ms 228268 KB Output is correct
16 Incorrect 4673 ms 263768 KB Output isn't correct
17 Halted 0 ms 0 KB -