Submission #83776

#	Time	Username	Problem	Language	Result	Execution time	Memory
83776		jcg	Factories (JOI14_factories)	C++14	15 / 100	2134 ms	525312 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#include <ext/algorithm>
#include <ext/numeric>

using namespace std;
using namespace __gnu_cxx;

typedef long long ll;

const ll oo = 0x3f3f3f3f3f3f3f3f;

vector<vector<pair<int, ll>>> adj;
vector<vector<pair<ll, int>>> table;
vector<int> tour, in, out, id;
vector<ll> depth;
vector<bool> inA, inB;

void Init(int N, int A[], int B[], int D[])
{
	adj.clear();
	adj.resize(N);

	for (int i = 0; i < N - 1; ++i)
	{
		adj[A[i]].push_back({B[i], D[i]});
		adj[B[i]].push_back({A[i], D[i]});
	}

	tour.clear();
	in = out = id = vector<int>(N);
	depth = vector<ll>(N);
	inA = inB = vector<bool>(N);

	function<void(int, int, ll)> dfs = [&](int u, int p, ll d)
	{
		in[u] = tour.size();
		depth[u] = d;
		tour.push_back(u);

		for (auto &e : adj[u])
			if (e.first != p)
			{
				dfs(e.first, u, d + e.second);
				tour.push_back(u);
			}

		out[u] = tour.size();
	};

	dfs(0, -1, 0);

	int logn = __lg(tour.size());

	table = vector<vector<pair<ll, int>>>(logn + 1, vector<pair<ll, int>>(tour.size()));

	for (int i = 0; i < tour.size(); ++i)
		table[0][i] = make_pair(depth[tour[i]], tour[i]);

	for (int i = 0; i < logn; ++i)
		for (int j = 0; j + (1 << i) < tour.size(); ++j)
			table[i + 1][j] = min(table[i][j], table[i][j + (1 << i)]);
}

bool ancestor(int u, int v)
{
	return in[u] <= in[v] && out[v] <= out[u];
};

int lca(int u, int v)
{
	if (in[u] > in[v])
		swap(u, v);
	int l = __lg(in[v] - in[u]);
	return u == v ? u : min(table[l][in[u]], table[l][in[v] - (1 << l)]).second;
};

long long Query(int S, int X[], int T, int Y[])
{
	vector<int> v;

	for (int i = 0; i < S; ++i)
		inA[X[i]] = true, v.push_back(X[i]);

	for (int i = 0; i < T; ++i)
		inB[Y[i]] = true, v.push_back(Y[i]);

	sort(v.begin(), v.end(), [&](int i, int j) { return in[i] < in[j]; });
	v.erase(unique(v.begin(), v.end()), v.end());

	for (int i = 0, k = v.size(); i + 1 < k; ++i)
		v.push_back(lca(v[i], v[i + 1]));

	sort(v.begin(), v.end(), [&](int i, int j) { return in[i] < in[j]; });
	v.erase(unique(v.begin(), v.end()), v.end());

	vector<vector<pair<int, ll>>> tree(v.size());
	vector<bool> A(v.size()), B(v.size());

	for (int i = 0; i < v.size(); ++i)
		id[v[i]] = i, A[i] = inA[v[i]], B[i] = inB[v[i]];

	vector<int> stk, nonroot(v.size());

	for (int &x : v)
	{
		while (!stk.empty() && !ancestor(stk.back(), x))
			stk.pop_back();

		if (!stk.empty())
		{
			nonroot[id[x]] = true;
			tree[id[stk.back()]].push_back({id[x], depth[x] - depth[stk.back()]});
		}

		stk.push_back(x);
	}

	assert(count(nonroot.begin(), nonroot.end(), 0) == 1);

	ll ans = oo;

	function<pair<ll, ll>(int, ll)> go = [&](int u, ll d)
	{
		ll a = A[u] ? d : oo;
		ll b = B[u] ? d : oo;

		if (a != oo && b != oo)
			ans = 0;

		for (auto &e : tree[u])
		{
			pair<ll, ll> ch = go(e.first, d + e.second);
			
			ans = min(ans, ch.first + b - 2 * d);
			ans = min(ans, ch.second + a - 2 * d);

			a = min(a, ch.first);
			b = min(b, ch.second);
		}

		return make_pair(a, b);
	};

	go(0, 0);

	for (int i = 0; i < S; ++i)
		inA[X[i]] = false;

	for (int i = 0; i < T; ++i)
		inB[Y[i]] = false;

	return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < tour.size(); ++i)
                  ~~^~~~~~~~~~~~~
factories.cpp:61:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j + (1 << i) < tour.size(); ++j)
                   ~~~~~~~~~~~~~^~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:100:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); ++i)
                  ~~^~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67